codeforces D. Cutting Out +二分

题目链接：http://codeforces.com/contest/1077/problem/D
题目大意：

给你n个的整数的主序列，要求你在主序列中找k个的整数。
然后在主序列中删除这k个数字，如果主序列还有这k个整数，可以继续删除。

输出能使删除次数最多的k的数字。

样例1， 2， 3的数字都在主串中出现了2次。所以输出次数为2。已经是最大的。

思路：开始用了贪心。统计了所有的数字出现次数。在拿出前k个

while(如果其中最小的次数*2<最大的次数)
{
删除最小的次数。最大的次数。
添加最大的次数/2, 最大的次数-(最大的次数/2)。
}
一直WA4，现在贪心发现了问题。例如：
9 3 1 1
第一次循环
5 4 3 1
第二次循环
4 3 2 3
那么最大的次数是2

实际上可以分成3 3 3 3
那么最大的次数是3

贪心显然不能做，不过这个复杂度至少要nlogn才能过，所以可以考虑二分，把删除的次数二分l=1; r=n;

思考：复杂度为nlogn时除了STL还可以考虑二分，自己往往一直用STL。下次还是要多考虑一下二分。

#include<bits/stdc++.h>
using namespace std;

int a[200005];

int pd(int mid, int k)
{
    int m=mid, key=0;
    for(int i=0;i<200005;i++)
    {
         if(a[i]>=m)
            key+=a[i]/m;

         if(key>=k)
            return 1;
    }
    return 0;
}

int main()
{
    fill(a, a+200005, 0);
    int n, k;
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++)
    {
        int t;
        scanf("%d",&t);
        a[t]++;
    }
    int l=1;
    int r=n;
    int w=0;

    while(l<=r)//二分
    {
        int mid=(l+r)/2;
        int p=pd(mid, k);
        if(p)
            l=mid+1, w=mid;
        else
            r=mid-1;

    }
    
    for(int i=0;i<200005;i++)//按照删除次数找元素输出
    {
         if(a[i]>=w)
         {
             int t=a[i]/w;
             while(t--)
             {
                 printf("%d ",i);
                 k--;
                 if(k==0)
                 {
                     printf("\n");
                     return 0;
                 }
             }
         }

    }
    printf("\n");

    return 0;
}