題意：給你n個數字，其中有的數字會重復出現（但最多出現3次），問你如何安排這些數字，可以使得相同數字之間的最小間隔最大。不需要打印具體的安排策略，只要求出最大的最小間隔即可。

這里首先要搞明白，最小間隔指的是什么。比如說3 4 5 3 6 3 4，這里的最小間隔就是1（題目規定間隔為j - i - 1），3的間隔有2，1兩種，4的講個是4 。但是要求的是最小間隔，所以取這些間隔中的最小值2 。

經過思考不難發現，因為最多出現3次，那么假如有出現3次的數字，我們肯定是順著排，比如說1 1 2 1 2 2 這個，我們排好一定是1 2 1 2 1 2，如果是三組或者更多出現三次的數字效果也是一樣的。出現三次的數字在這樣排布之后，一共有三部分，每部分的數字不同。這三部分形成了兩個間隔，那么，不難想到，假如我們要求最小間隔最大，那么如果有二次出現的數字，一定是均勻分開，填充到這兩個間隔中取。對于出現1次的數字，一次放到間隔I，一次放到間隔II，重復這個過程。也就是說，出現1次的數字，只有有偶數個的時候才會增加最小間隔。

如果沒有出現3次的數字呢？對于多組出現2次的數字，我們的策略跟上面出現3次的是一樣的。分成兩部分，每部分數字不同。假如有出現1次的數字，就往這兩部分形成的間隙中填充。這里與三次的間隙不同，1次數字不論奇偶，放進去多少個，間隔就增加多少。

分析完之后，我們解決問題的關鍵就變成了：如何統計出現3次、2次、1次數字的數量？

這里也是我當時一直卡住的點。我想用類似桶排的思想，數組的標號表示數字的值，但是，因為數字的范圍是1e9所以必然會超。之后又想到，因為總個數是1e5，事前又不能確定n的大小，可以采用向量。
但是我讀完放入向量之后，先進行sort排序，然后再用count來查詢在整個vector中出現的次數。其實如果要用count，就沒必要sort，sort之后完全可以回到下面AC代碼中的判斷方法。count，復雜度是O(n)，加上前面的部分，所以TLE 。

今天補題的時候看到別人的方法，感覺自己真的蠢……統計出現的次數，sort之后相同元素都會在一起，我們記錄不同元素下標之間的差，其實就是前一元素的數目，那只要O(n)掃一遍即可。

其實昨晚我最后的vector方法已經非常接近……也使用了記錄上一不同值及其下標進行計算的方法，但是明明已經sort了還要用count查詢，就很蠢……應該就是n次計算，每次都調用count導致了TLE。

最后還有一個坑。就是用數組統計個數的時候，究竟怎么計算的問題。我的lastmark記錄的是最新不同元素的第一個的下標，一旦不同，進入這個分支我們cnt[__] 中 __ 統計的不是當前元素是3次2次還是1次，而是上一元素的，所以不需要+1（因為我們當前的坐標i本身就是新元素的第一個而不是上一元素的最后一個）。
還有就是對于最后一個位置，是很特殊的，因為我們到n-1就跳出，所以最后一次可能會來不及更新。最后一個位置有兩種情況，一種是，最后一個元素它只出現了一次，那么就直接cnt[1]++即可；另一種情況是它出現了多次，但是這里要注意：我們此時i表示的是當前元素的最后一個的下標，而不同于上面對1~n-1的元素處理時表示新元素的第一個，所以這里要+1才是正確的！（因為這里WA了好久……想破頭才發現是這里錯了（。

#include <bits/stdc++.h>using namespace std;int n, ans; int cntset[4];int main() {scanf("%d", &n);const int size_ = n;int numset[size_];memset(numset, 0, sizeof(numset));//0 - n-1讀入n個數字for(int i = 0;i < n;i++)scanf("%d", &numset[i]);sort(numset, numset+size_);//排序int lastcon = -1, //上一次記錄的成語lastmark = 0; //第一個不同數字出現的位置for(int i = 0;i < n;i++){//printf("numset[%d] = %d\n", i, numset[i]);if(numset[i] != lastcon){cntset[i-lastmark]++;//實際統計的不是當前的數字，而是上一個lastcon = numset[i];//當前數字是新一種數字的第一個lastmark = i;}if(i == n-1)//最后一個元素{if(lastmark == i)cntset[1]++;else//前面還有cntset[i-lastmark+1]++;}}if(cntset[3])//均只出現一次ans = cntset[3]-1+cntset[2]+cntset[1]/2;else if(cntset[2])//只有2 1ans = cntset[2]-1+cntset[1];elseans = n;printf("%d\n", ans);return 0; }

總結

以上是生活随笔為你收集整理的CometOJ #10 沉鱼落雁 | 思维的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。