【例84.2】分香蕉

解题思路

香蕉质量降序，猴子按体重降序并记录原编号。第i个香蕉给排序第i%m只猴子，累加到其原编号，最后按原猴子顺序输出。

正确性说明

依照上述推导，逐步维护已处理部分的有效状态。每一步都完成当前项的贡献且不改变已确定的次序，结束时输出的状态恰好对应题目要求。

易错点

若出现同体重，题面未给额外规则，代码按原编号先后固定次序；质量总和用long long。

复杂度

时间O(n log n+m log m)，空间O(n+m)。

参考代码（C++11）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<long long> a(n), weight(m), ans(m);
    for (auto &x : a)
        cin >> x;
    for (auto &x : weight)
        cin >> x;
    vector<int> id(m);
    iota(id.begin(), id.end(), 0);
    stable_sort(id.begin(), id.end(),
                [&](int x, int y) { return weight[x] > weight[y]; });
    sort(a.begin(), a.end(), greater<long long>());
    for (int i = 0; i < n; i++)
        ans[id[i % m]] += a[i];
    for (int i = 0; i < m; i++) {
        if (i)
            cout << " ";
        cout << ans[i];
    }
    cout << "\n";
    return 0;
}