1 初步想法

1.1 前置知識：vector數組的去重操作

unique()將不重復的元素放在數組前面，重復元素移到后面，qs獲取不重復元素的后一個位置，之后用erase()函數去除重復元素。

qs=unique(a.begin()+1,a.begin()+k+1);
a.erase(qs,a.end());

1.2 模擬的解法

根據題目意思，統計數組中不同數的種類數，然后遍歷數組，每次減去種類數，直到數組中的元素只有一種為止。在實現上，我的輸入的數是從數組a下標1開始，所以我設置的循環條件是a.size()>2,因為a[0]=0，如果碰到輸入n個相同的非零整數，此時去重后元素的個數是2。

實現代碼（運行超時，只通過30%左右的數據）

#include<bits/stdc++.h>
using namespace std;
int n;
vector<long long> a(100005);
void process(){int k=a.size()-1;for(int i=1;i<=a.size();i++){if(a[i]-k>0) a[i]=a[i]-k;else a[i]=0;}vector<long long>::iterator qs;sort(a.begin()+1,a.begin()+k+1);qs=unique(a.begin()+1,a.begin()+k+1);a.erase(qs,a.end());
}
int main(){cin>>n;for(int i=1;i<=n;i++) cin>>a[i];vector<long long>::iterator qs;sort(a.begin()+1,a.begin()+n+1);qs=unique(a.begin()+1,a.begin()+n+1);a.erase(qs,a.end());long long cnt=0;while(a.size()>2){process();cnt++;}cout<<cnt;return 0;
}

不過這種解法的問題是會超時，數據規模是10的5次方，main函數的while循環加上函數process()里面也有一重循環，效率不高，要想一種新的解法。

2 新方法

2.1 新方法的思想

我設計以下測試樣例：

測試樣例1
4
100 200 300 400

對于測試樣例1，排序后，我們知道100是最先變化為0的，100在減小為0的過程中，種類數已知是4個，所以，100減為0需要進行100/4=25次操作。之后在剩下的數中，100減為0后依次變為100，200，300（是所有數同時減100），對于這里的100要變成0，因為目前數組有4，100，200，300這4種數，需要經過100/4=25次操作。之后，剩下的數以此為100，200，因為目前數組有4，100，200這3種數，100變成0需要經過100/3+1=34次操作（目前數組有），然后剩下一個數98，需要經過98/2=49次操作。一共是25+25+34+49=133次操作。通過這樣的做法我們可以降低時間復雜度。

2.2 新方法的實現

為了實現新方法，在數組各元素減為0的過程中，我們要設置幾個變量：
ans：最終結果
sum：累計減少量
cnt：當前的種類數，對于非0元素，如果不是第一個，因為前面的數已經變成0，所以非第一個數需要+1，把0算進去。cnt=a.size()-i+(i!=0);
x：表示當前的數變為0需要操作的次數，我們需要向上取整：x=(a[i]-sum+cnt-1)/cnt。

實現代碼

#include<bits/stdc++.h>  // 包含所有標準庫頭文件
#define LL long long    // 定義長整型別名
int n;
using namespace std;int main(){cin>>n;  // 輸入數組長度vector<LL> a(n);  // 創建長度為n的長整型向量for(int i=0;i<n;i++) cin>>a[i];  // 輸入數組元素// 排序并去重，確保數組是升序且無重復元素sort(a.begin(),a.end());a.erase(unique(a.begin(),a.end()),a.end());// 如果數組只有一個元素，直接輸出0if(a.size()==1)cout<<0<<endl;else{LL ans=0,sum=0,cnt=0;  // ans:結果，sum:累計減少量，cnt:當前影響的元素數量// 遍歷去重后的數組for(int i=0;i<n;i++){// 如果當前元素減去累計減少量已經小于0，跳過if(a[i]-sum<0) continue;// 計算當前影響的元素數量：剩余元素數 + (如果不是第一個元素，還包括之前的元素)cnt=a.size()-i+(i!=0);// 計算需要多少次操作才能將當前元素減為0// (a[i]-sum+cnt-1)/cnt 是向上取整的技巧LL x=(a[i]-sum+cnt-1)/cnt;ans+=x;  // 累計操作次數sum+=x*cnt;  // 更新累計減少量}cout<<ans<<endl;}return 0;
}

參考

b站講解