526互联

Educational Codeforces Round 34 (Rated for Div. 2) C(multiset、思维)

发布时间 2023-09-13 00:55:21作者: yanhy-orz

C. Boxes Packing
思路：每一次选择一段递增的子段, 将其删除, 最高的一个会能够被看到。这个过程可以用 std::multiset 模拟, 主要是两个函数的应用：
extract(x)：删除集合中的一个 $ x $，upper_bound(x)：返回集合中第一个大于 $ x $ 的元素的迭代器, 找不到返回 end()。每一个元素会被删除一次, 时间复杂度为 $ O(nlog_2n) $。

点击查看代码 
#include <bits/stdc++.h>
using i64 = long long;

inline i64 read() {
    bool sym = false; i64 res = 0; char ch = getchar();
    while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return sym ? -res : res;
}

int main() {
    int n = read(), ans = 0;
    std::vector<int> a(n + 1);
    std::multiset<int> s;
    for (int i = 1; i <= n; i++) {
        a[i] = read(); s.insert(a[i]);
    }
    while (s.size()) {
		ans++; 
        int now = *s.begin();
        s.extract(now);
        auto it = s.upper_bound(now);
        while (it != s.end()) {
			now = *it;
			s.extract(now);
			it = s.upper_bound(now);
        }
    }
    printf("%d\n", ans);
    return 0;
}