题目链接(abc227_D)

代码:

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
long long a,b,ax[200001],l,r,mid,sum,sumx,bx,cnt;
inline bool cmp(long long x,long long y)
{
	return x>y;
}
inline bool check(long long k)
{
	cnt=sumx=0,bx=b; 
	for(long long i=1;i<=a;i++)
	{
		if(ax[i]>=k)cnt++;
		else sumx+=ax[i];
	}
	if(cnt>=bx)return true;
	bx-=cnt;
	if(sumx>=k*bx)return true;
	return false;
}
int main()
{
	scanf("%lld%lld",&a,&b);
	for(long long i=1;i<=a;i++)
	{
		scanf("%lld",&ax[i]);
		sum+=ax[i];
	}
	sort(ax+1,ax+a+1,cmp);
	l=1;r=sum;
	while(l<r-1)
	{
		mid=(l+r)>>1;
		if(check(mid))l=mid;
		else r=mid;
	}
	printf("%lld",l);
}

思路:二份答案(1.如果不小于mid的数的数量大于$k$,一定有解,否则k-=x;2如果剩余数的和大于k*mid，则一定有解)