結構雰囲気で解いてしまった。 まず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; }