二分
虽然这是一道简单的二分,但是做完这个题将我对二分有了新的理解
0. 大多数情况下,二分问题的序列是非递减的
1. 其次,二分有两种情况,一种是找序列的左端点,另一种是右端点
2. 左端点要在所有满足check()函数的情况下,使r=mid;不满足的情况下l=mid+1;
3. 右端点要在所有满足check()函数的情况下,使l=mid+1;不满足的条件下 r=mid;
4. 因为找右端点的时候 mid=l+r+1>>1. 所以,特别的 l=mid, r=mid-1;
5. 对于check()函数,本质上是一个<=或者>=的选择
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef long long ll;
int n,m;
const int N=1e6+10;
ll a[N];
int res;
ll check(int x)
{
ll res=0;
for(int i=0;i<n;i++) if(a[i]>x) res+=a[i]-x;
return res;
}
int find(int x)
{
int l=0,r=a[n-1];
while(l<r)
{
int mid=l+r+1>>1;
if(check(mid)>=x) l=mid;
else r=mid-1;
}
return r;
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++) cin>>a[i];
sort(a,a+n);
cout<<find(m)<<endl;
return 0;
}