B - Village of M People

atcoder.jp

結構雰囲気で解いてしまった。 まずceil(AiM/N)でBiをざっくり求める。 Biの合計値を算出したら、Mと差分が出るので、max(BiN - AiM)が最小になるように、Biの値を減らしていく。 max(BiN - Ai*M) が大きい順に減らしていきたいので、PriorityQueueで管理する。

void solve(long long K, long long N, long long M, std::vector<long long> A){
    vl B(K+9);
    vector<pair<ll,ll>> diff(K+9);
    priority_queue<pair<ll,ll>> que;
    ll s = 0;
    REP(i, K) {
        B[i] = (A[i]*M+N-1)/N;
        s += B[i];
        que.push({B[i]*N-A[i]*M, i});
    }
 
    REP(i, s-M) {
        ll bi = que.top().second;
        que.pop();
        B[bi]--;
        que.push({B[bi]*N-A[bi]*M, i});
    }
 
    REP(i, K) {
        if (i!=0) cout << " ";
        cout << B[i];
    }
    cout << endl;
}