算法

(排序) $O(n\log n)$

首先每个人分配到 $\lfloor \frac{K}{N} \rfloor$ 个糖，而对于剩下的 $K \% N$ 个糖分配给 ID 号前 $K \% N$ 小的人。

C++ 代码

// 写法1
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::vector;
using ll = long long;
using P = std::pair<int, int>;

int main() {
    int n;
    ll k;
    cin >> n >> k;

    vector<int> a(n);
    rep(i, n) cin >> a[i];

    vector<ll> ans(n, k / n);
    k %= n;
    vector<P> p(n);
    rep(i, n) p[i] = P(a[i], i);
    sort(p.begin(), p.end());
    rep(i, k) ans[p[i].second]++;

    rep(i, n) cout << ans[i] << '\n';

    return 0;
}

// 写法2
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::vector;
using ll = long long;
using P = std::pair<int, int>;

int main() {
    int n;
    ll k;
    cin >> n >> k;

    vector<int> a(n);
    rep(i, n) cin >> a[i];

    vector<ll> ans(n, k / n);
    k %= n;

    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
//  rep(i, n) p[i] = i;
    sort(p.begin(), p.end(), [&](int i, int j) {
        return a[i] < a[j];
    });
    rep(i, k) ans[p[i]]++;

    rep(i, n) cout << ans[i] << '\n';

    return 0;
}