P7557 [USACO21OPEN] Acowdemia S

典型二分：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
int n,a[N],k,l;
bool check(int x) {
 
	int cnt=0,ans=0;
	for(int i=1; i<=x; i++) {
		if(a[i]>=x) {
			cnt++;
			continue;
		}
		else{
			if(x-a[i]>k)return false;
			else{
			ans=ans+x-a[i];	
			}
		}
	}
	return ans<=k*l;
}
bool cmp(int i,int j) {
	return i>j;
}
void solve() {
	cin>>n>>k>>l;
	for(int i=1; i<=n; i++) cin>>a[i];
	sort(a+1,a+1+n,cmp);
	int l=-1,r=n+1;
	while(l+1<r) {
		int mid=l+r>>1;
		if(check(mid))l=mid;
		else r=mid;
	}
	cout<<l<<"\n";
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int t=1;
	//cin>>t;
	while(t--) {
		solve();
	}
	return 0;
}
 
 
 
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
int n,a[N],k,l;
bool check(int x) {
 
	int cnt=0,ans=0;
	for(int i=1; i<=x; i++) {
		if(a[i]>=x) {
			cnt++;
			continue;
		}
		else{
			if(x-a[i]>k)return false;
			else{
			ans=ans+x-a[i];	
			}
		}
	}
	return ans<=k*l;
}
bool cmp(int i,int j) {
	return i>j;
}
void solve() {
	cin>>n>>k>>l;
	for(int i=1; i<=n; i++) cin>>a[i];
	sort(a+1,a+1+n,cmp);
	int l=-1,r=n+1;
	while(l+1<r) {
		int mid=l+r>>1;
		if(check(mid))l=mid;
		else r=mid;
	}
	cout<<l<<"\n";
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int t=1;
	//cin>>t;
	while(t--) {
		solve();
	}
	return 0;
}
 
 
 

over~