1. 題目

N 個人在玩游戲，每局游戲有一個裁判和 N-1 個平民玩家。給出一個數(shù)組 A, A[i] 代表玩家 i 至少需要成為平民 A[i] 次，返回最少進行游戲的次數(shù)。

樣例 1: 輸入：A = [2, 2, 2, 2] 輸出：3 解析： A[0] = 2表示玩家0至少需要成為2次平民 第一局：玩家0擔(dān)任裁判，此時 A[0] = 0, A[1] = 1, A[2] = 1, A[3] =1 第二局：玩家1擔(dān)任裁判，此時 A[0] = 1, A[1] = 1, A[2] = 2, A[3] = 2 第三局：玩家2擔(dān)任裁判，此時 A[0] = 2, A[1] = 2, A[2] = 2, A[3] = 3 此時每個玩家都達到了要求，所以進行三局游戲即可樣例 2: 輸入：A = [84,53] 輸出：137 解析： 第一局：玩家1擔(dān)任裁判 ，此時 A[0] = 1, A[1] = 0 ...... 第三十一局：玩家1擔(dān)任裁判，此時 A[0] = 31, A[1] = 0 第三十二局：玩家0擔(dān)任裁判，此時 A[1] = 31, A[1] = 1 第三十三局：玩家1擔(dān)任裁判，此時 A[1] = 32, A[1] = 1 第三十四局：玩家0擔(dān)任裁判，此時 A[1] = 32, A[1] = 2 ...... 第一百三十七局：玩家1擔(dān)任裁判，此時 A[1] = 84, A[1] = 53 此時每個玩家都達到了要求，所以進行一百三十七局游戲即可注意事項 ∑Ai <= 1e18 1 < n < 1000

2. 解題

• 直接的想法是，次數(shù)最少的那個人當裁判，其他人 -1
• 然后再排序，重復(fù)以上過程，模擬，數(shù)據(jù)數(shù)字非常大，會超時

---

• 先排序，除最大的人MAX外，其余人都減去 MAX
• 前面這 n-1 人的和（一個負數(shù)，可以當裁判的次數(shù)）
• 如果這個數(shù)的絕對值（當裁判次數(shù)）> MAX，那么直接 MAX次游戲結(jié)束
• 否則，裁判次數(shù)不夠，需要補的次數(shù) / n-1 個人來均攤

class Solution { public:long long playGames(vector<int> &A) {// Write your code heresort(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;elsereturn ceil((sum+MAX)/double(n-1))+MAX;} };

100% 數(shù)據(jù)通過測試
總耗時 50 ms
您的提交打敗了 54.05% 的提交!

class Solution { //超時，模擬代碼 public:long long playGames(vector<int> &A) {// Write your code hereint 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;} };

總結(jié)

以上是生活随笔為你收集整理的LintCode 1671. 玩游戏（贪心、难）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。