练26.2 分苹果

解题思路

把每人所得排序为 b1<b2<…<bn。因为都是正整数，所以 bk≥k，至少需要 1+2+…+n=n(n+1)/2 个，分配 1～n 个恰能达到下界。

正确性说明

任意合法分配总量不小于该公式；分配第 k 人 k 个达到公式，因此它就是最小值。

易错点

每人都要有苹果，不能从 0 个开始。

复杂度

时间 O(1)，空间 O(1)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n;
    cin >> n;
    cout << n * (n + 1) / 2 << "\n";
    return 0;
}