題目描述

小可可的學校信息組總共有?n?個隊員，每個人都有一個實力值?ai?。現在，一年一度的編程大賽就要到了，小可可的學校獲得了若干個參賽名額，教練決定把學校信息組的?n?個隊員分成若干個小組去參加這場比賽。

但是每個隊員都不會愿意與實力跟自己過于懸殊的隊員組隊，于是要求分成的每個小組的隊員實力值連續，同時，一個隊不需要兩個實力相同的選手。舉個例子：[1,2,3,4,5]?是合法的分組方案，因為實力值連續；[1,2,3,5]?不是合法的分組方案，因為實力值不連續；[0,1,1,2]?同樣不是合法的分組方案，因為出現了兩個實力值為?1?的選手。

如果有小組內人數太少，就會因為時間不夠而無法獲得高分，于是小可可想讓你給出一個合法的分組方案，滿足所有人都恰好分到一個小組，使得人數最少的組人數最多，輸出人數最少的組人數的最大值。

注意：實力值可能是負數，分組的數量沒有限制。

輸入格式

輸入有兩行：

第一行一個正整數?n，表示隊員數量。

第二行有?n?個整數，第?i?個整數?ai??表示第?i?個隊員的實力。

輸出格式

輸出一行，包括一個正整數，表示人數最少的組的人數最大值。

輸入輸出樣例

輸入 #1復制

7
4 5 2 3 -4 -3 -5

輸出 #1復制

3

說明/提示

樣例解釋

分為?2?組，一組的隊員實力值是?[4,5,2,3]，一組是?[?4,?3,?5]，其中最小的組人數為?3，可以發現沒有比?3?更優的分法了。

數據范圍

對于?100%?的數據滿足：1≤n≤105，∣ai?∣≤109。

本題共?10?個測試點，編號為?1～10，每個測試點額外保證如下：

測試點編號	數據限制
1～2	n≤6,1≤ai?≤100
3～4	n≤1000,1≤ai?≤105?且?ai??互不相同
5～6	n≤105，ai??互不相同
7～8	n≤105,1≤ai?≤105
9～10	n≤105,?109≤ai?≤109

思路：需要得到最后的分組策略中，含最小人數的要在所有分組策略中最多。那么意味著，如果我現在有多個分組的人具備x的實力值的人，此時來了一個x+1實力值的人，因為要最大化最少人數的拿個分組的人數，那么我們的貪心策略就是：要將此時這個x+1實力值的人放到當前人數最小的組中。

實現：由于每個組中的人的實力值需要連續且不重復，所以我們考慮對實力值進行排序。因為在來了一個新的數時，每個組都要被考慮是否放進去，判斷條件：當前組中的最后一個數是否比當前數少一，在這個基礎上，找出人數最少的那個組。所以我們需要維護每個組的狀態，但是我們又不需要維護每個數，由于一開始對數組進行了排序，所以我們只需要維護每個組的最后一個數。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;typedef struct Group{int x,y;bool operator<(Group g) const{return x<g.x;}	
}G;int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n;cin>>n;int nums[n];for(int i=0; i<n; i++) cin>>nums[i];sort(nums,nums+n);int q[n],qLen[n];int qnums = 0;for(int i=0; i<n; i++){int now = nums[i];int minLen = INT_MAX;int InsertIndex = -1; 		for(int j=0; j<qnums; j++){if(q[j]+1==now&&minLen>qLen[j]){minLen = qLen[j];InsertIndex = j;	}	}if(InsertIndex==-1){q[qnums] = now;qLen[qnums] = 1;qnums++;}else{q[InsertIndex]=now;qLen[InsertIndex]++;}}int minn = INT_MAX;for(int i=0; i<qnums; i++){minn = min(minn, qLen[i]);}cout<<minn<<endl;return 0;
}

但是，這樣并不會通過所有的測試樣例！！！！最后一個點會超時，我們考慮進行優化

可以發現我們每次都要找人數最少的那個組，那我們能不能搜索的再快一點呢？可以，直接使用二分搜索。

我們每次在找組的時候，都將此時這個數放到最右邊的那個地方，這樣我們就可以一直保證人數最少的會被變大。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;typedef struct Group{int x,y;bool operator<(Group g) const{return x<g.x;}	
}G;int bineray(int x,int l,int r,int *q){while(l<=r){int mid = l+(r-l)/2;if(q[mid]<=x) l=mid+1;else r=mid-1;}return q[l-1]==x?l-1:-1;
}int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n;cin>>n;int nums[n];for(int i=0; i<n; i++) cin>>nums[i];sort(nums,nums+n);int q[n],qLen[n];int qnums = 0;for(int i=0; i<n; i++){int now = nums[i];int InsertIndex = bineray(now-1,0,qnums-1,q);if(InsertIndex==-1){q[qnums] = now;qLen[qnums] = 1;qnums++;}else{q[InsertIndex]=now;qLen[InsertIndex]++;}}int minn = INT_MAX;for(int i=0; i<qnums; i++){minn = min(minn, qLen[i]);}cout<<minn<<endl;return 0;
}