SRM504.5 Div1 Medium(550) TheJackpotDivOne

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;
}};