SRM504.5 Div1 Medium(550) TheJackpotDivOne
全員が同じ金額になったら1ドルずつ配るだけなので、まとめて計算できる。全員の金額の合計はlong longに収まりきれないので対策が必要。人数をnとして、nで割った商と余りで計算するとか。Javaを覚えるか多倍長整数クラスを用意するべきなのだろうか。
#include <vector> #include <algorithm> using namespace std; class TheJackpotDivOne{public: vector<long long> find( vector<long long> money, long long jackpot ) { int n = (int)money.size(); while ( jackpot > 0 ) { // 全員が同額になったら終了 bool flat = true; for ( int i=1; i<n; i++ ) if ( money[i] != money[0] ) flat = false; if ( flat ) { money = vector<long long>( n, money[0]+jackpot/n ); for ( int i=0; i<(int)(jackpot%n); i++ ) money[n-i-1]++; return money; } long long sumh = 0; // /n long long suml = 0; // %n for ( int i=0; i<n; i++ ) { suml += money[i]; sumh += suml/n; suml %= n; } long long avg = sumh+suml/n; int p = 0; for ( int i=0; i<n; i++ ) if ( money[i] < money[p] ) p = i; long long X = avg - money[p] + 1; money[p] += min(X,jackpot); jackpot -= X; } sort(money.begin(),money.end()); return money; }};