给定一个初始序列 {1, 2, . . . , n}，你需要进行若干次操作，将整个序列所有数变成零。每个操作由三步 组成： 1. 选择一个下标集合 S = {i1, i2, . . . , ik} ⊆ {1, 2, . . . , n}； 2. 选择一个非负整数 x； 3. 对每个选中的数减去 x：∀i ∈ S, ai ← ai − x。 请计算在最优策略下需要的操作次数。 输入 输入一行一个正整数 n (1 ≤ n ≤ 106 )。 输出 输出一行一个正整数，表示最少需要的操作次数。 样例 standard input standard output 1 1 2 2 3 2 注释 对于第三组样例，一种最优方案的两次操作如下： 1. S = {1, 3}, x = 1 : a = {0, 2, 2}; 2. S = {2, 3}, x = 2 : a = {0, 0, 0}. 可以证明，没有次数更少的方案。

代码如下：

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 1e6 + 5;
int n;
int b[MAXN];

int main() {
    cin >> n;
    int ans = 0;
    for (int i = n; i >= 1; i--) {
        int j = 0;
        for (int k = 1; k <= n/i; k++) {
            int l = (k-1)*i + 1, r = k*i;
            int x = min(b[l], i);
            while (j < i && x > 0) {
                int y = min(b[l+j+1], x);
                b[l+j+1] -= y;
                x -= y;
                j++;
            }
            ans += j > 0;
        }
        b[i] += j;
    }
    cout << ans << endl;
    return 0;
}

这个算法的时间复杂度为 O(n log n)，可以通过本题。