LintCode 1671. 玩游戏（贪心、难）

样例 1:
输入：A = [2, 2, 2, 2]
输出：3
解析：
A[0] = 2表示玩家0至少需要成为2次平民
第一局：玩家0担任裁判，此时 A[0] = 0, A[1] = 1, A[2] = 1, A[3] =1
第二局：玩家1担任裁判，此时 A[0] = 1, A[1] = 1, A[2] = 2, A[3] = 2
第三局：玩家2担任裁判，此时 A[0] = 2, A[1] = 2, A[2] = 2, A[3] = 3
此时每个玩家都达到了要求，所以进行三局游戏即可

样例 2:
输入：A = [84,53]
输出：137
解析：
第一局：玩家1担任裁判 ，此时 A[0] = 1, A[1] = 0
......
第三十一局：玩家1担任裁判，此时 A[0] = 31, A[1] = 0 
第三十二局：玩家0担任裁判，此时  A[1] = 31, A[1] = 1
第三十三局：玩家1担任裁判，此时  A[1] = 32, A[1] = 1
第三十四局：玩家0担任裁判，此时  A[1] = 32, A[1] = 2
......
第一百三十七局：玩家1担任裁判，此时  A[1] = 84, A[1] = 53
此时每个玩家都达到了要求，所以进行一百三十七局游戏即可

注意事项
∑Ai <= 1e18
1 < n < 1000

class Solution {
public:
    long long playGames(vector<int> &A) {
        // Write your code here
        sort(A.begin(),A.end());
        int n = A.size();
        int MAX = A[n-1];
        long long sum= 0;
        for(int i = 0; i < n-1; ++i)
        {
            A[i] -= MAX;
            sum += A[i];
        }    
        if(sum + MAX <= 0)
            return MAX;
        else
            return ceil((sum+MAX)/double(n-1))+MAX;
    }
};

class Solution {	//超时，模拟代码
public:
    long long playGames(vector<int> &A) {
        // Write your code here
        int n =  A.size(), i, c;
        if(n == 2)
            return A[0]+A[1];
        long long sum = 0;
        sort(A.begin(),A.end());
        while(A[0] > 0)
        {
            i= n-2;
            while(i >= 2 && A[n-1] == A[i])
                i--;
            c = A[n-1]-A[i];
            if(c==0)
                c = 1;
            sum += c;
            for(i = n-1; i >= 1; i--)
                A[i] -= c;
            sort(A.begin(),A.end());
        }
        if(A[n-1] > 0)
            sum += A[n-1];
        return sum;
    }
};