SRM 504.5 Div1 medium TheJackpotDivOne

問題概要

47人の人がいる。
あなたは10^18円くらいお金をもっている。
みんなそれぞれお金を持ってる。
一番お金が少ない人に対して、全員の平均より大きいの最小の整数円
になるようにお金をわたす。
たりない場合はありったけ渡す。
お金がある間繰り返す。
最終的にこの人たちの所持金を答えよ。

解法

実際にやる。
実際にやると、あることに気づく。

• 最大の所持金は全員のお金が一致するまで変化しない
• 全員が一致すると、全員に1円ずつ、順番にお金がなくなるまで渡せばよい。

そして、

• 全員の所持金が一致するまでそんなに時間がかからない。

ではなぜか。
それは、

• 最低でも、一番小さい値と一番大きい値の差の1/47は一番小さい値は増える。

つまるところ、
だいたい、47 * 47回繰り返せば全部一致する。
全部一致してからは、

• 全員が一致すると、全員に1円ずつ、順番にお金がなくなるまで渡せばよい。

ので、計算で求められる。
平均の計算がlong longでもあふれるので、工夫して平均とったほうがいい。

ソース

#include<algorithm>
#include<vector>

#define REP(i,b,n) for(int i=b;i<(int)n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)

using namespace std;
long long ave(vector<long long> v){
  unsigned long long sum = 0;
  unsigned long long ave = 0;
  FOR(it, v){
    ave += *it/v.size();
    sum += *it%v.size();
  }
  unsigned long long ret = ave + sum / v.size() + 1;
  return ret;
}
class TheJackpotDivOne {
public:
  vector<long long> find(vector<long long> money, long long n) {
    sort(ALL(money));
    while(money.front() != money.back() && n > 0){
      long long A = ave(money);
      long long D = A - money.front();
      money.front() += min(D, n);
      n -= min(n, D);
      sort(ALL(money));
    }
    if(n <= 0)return money;
    FOR(it, money){
      *it += n / money.size();
    }
    sort(ALL(money));
    int ret = n % money.size();
    rep(i, ret){
      money[i]++;
    }
    sort(ALL(money));
    return money;
  }
};