http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1686
题意：
思路：
第K大值，所以可以考虑二分法，然后用尺取法去扫描，但是直接扫描肯定是不行的，数太大，数组开不了那么大。
没想到可以用离散化来预处理，就是先将数组排序、去重，然后对于序列中的每一个数，计算出它的lower_bound值，原来相同的数肯定还是相同的，因为n小于等于1e5,所以原来很大的值，经过这样处理之后就会变得很小了。
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int maxn = 1e5 + 5; 7 8 int a[maxn], b[maxn]; 9 int cnt[maxn]; 10 int n; 11 int k; 12 13 bool check(int x) 14 { 15 int count=0; 16 memset(cnt,0,sizeof(cnt)); 17 int L=1,R=1; 18 while(R<=n) 19 { 20 cnt[a[R]]++; 21 if(cnt[a[R]]>x) 22 { 23 count+=n-R+1; 24 cnt[a[L]]--; 25 L++; 26 while(cnt[a[R]]>x && L<R) 27 { 28 count+=n-R+1; 29 cnt[a[L]]--; 30 L++; 31 } 32 } 33 R++; 34 if(count>=k) return true; 35 } 36 return false; 37 } 38 39 int main() 40 { 41 //freopen("D:\\input.txt","r",stdin); 42 while(~scanf("%d%d",&n,&k)) 43 { 44 for(int i=1;i<=n;i++) 45 { 46 scanf("%d",&a[i]); 47 b[i]=a[i]; 48 } 49 sort(b+1,b+n+1); 50 int num=unique(b+1,b+n+1)-(b+1); 51 for(int i=1;i<=n;i++) 52 a[i]=lower_bound(b+1,b+num+1,a[i])-(b+1); 53 54 //枚举第k大的值 55 int L=1,R=n; 56 while(L<=R) 57 { 58 int mid=(L+R)/2; 59 if(check(mid)) L=mid+1; 60 else R=mid-1; 61 } 62 cout<<L<<endl; 63 } 64 }
