代码(WA了Subtask2的#9):
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
int n,k,b[10000005],tmp,ans;
bool cmp(int x,int y)
{
return x > y;
}
int main()
{
cin >> n >> k;
for(int i = 1;i <= n;i++)
{
cin >> tmp;
b[tmp]++;
}
sort(b,b+n+1,cmp);
if(ceil(0.5*n) <= k) cout << "pigstd";
else if(b[0] <= k) cout << "pigstd";
else
{
if(k == 0)
{
if(b[0] == 1) cout << n;
else
{
for(ans = 0;ans <= n && b[ans] == b[0];ans++);
cout << ans;
}
}
else
{
if(b[0]-k > b[1]+k)
{
cout << 1;
return 0;
}
int i = 0,j,len = b[0];
while(ceil(1.0*(len-k)/(i+1)) <= b[i+1] && b[i+1]+k >= b[0]-k && i < n)
{
if(k >= b[i+1])
{
cout << "pigstd";
return 0;
}
j = i + 2;
while(b[j]+k >= b[i+1] && b[j]+k >= b[0]-k) j++;
len += b[++i];
}
cout << j;
}
}
}