不开龙long永远的痛!
不开龙long永远的痛!
不开龙long永远的痛!
不开龙long永远的痛!
不开龙long永远的痛!
//应该以最高的树为基准二分
初次尝试:
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
//应该以最高的树为基准二分
int n;
int m;
int a[1000010];
int maxx=-1;
int minn=100000;
bool check(int mid){
int high = 0;
for(int i=0;i<n;i++){
if(a[i] > mid){
high += (a[i] - mid);
}
}
if(high < m) return false;
return true;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
if(a[i] > maxx) maxx = a[i];//找到最高的
if(a[i] < minn) minn = a[i];
}
// printf("%d %d\n",minn,maxx);
// cout<<"****"<<endl;
int l= minn,r=maxx;
while(l<r){
//找右端点,右端小左
int mid = l+r+1 >> 1;
if(check(mid)){
l = mid;
// printf("llll%d\n",l);
}
else {
r = mid - 1;
// printf("rrrr%d\n",r);
}
}
cout<<l<<endl;
return 0;
}
结果:
AC代码:因为M的数据范围是2的9次方,需要开longlong,对应的判断函数里high的也要开成longlong。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
//应该以最高的树为基准二分
int n;
long long m;
int a[1000010];
int maxx=-1;
int minn=100000;
bool check(int mid){
long long high = 0;
for(int i=0;i<n;i++){
if(a[i] > mid){
high += (a[i] - mid);
}
}
if(high < m) return false;
return true;
}
int main()
{
scanf("%d%lld",&n,&m);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
if(a[i] > maxx) maxx = a[i];//找到最高的
if(a[i] < minn) minn = a[i];
}
// printf("%d %d\n",minn,maxx);
// cout<<"****"<<endl;
int l= minn,r=maxx;
while(l<r){
//找右端点,右端小左
int mid = l+r+1 >> 1;
if(check(mid)){
l = mid;
// printf("llll%d\n",l);
}
else {
r = mid - 1;
// printf("rrrr%d\n",r);
}
}
cout<<l<<endl;
return 0;
}
结果: