我对于二分有一点点疑问
查看原帖
我对于二分有一点点疑问
205320
peng_cheng楼主2021/7/29 22:03

这是我第一次提交的代码,50分。

#include<bits/stdc++.h>
using namespace std;
long long n,m;
long long a[1000005];
long long holl(long long now)
{
	long long ans = 0;
	for(long long i = 1;i <= n;i++)
	{
		if(now >= a[i])continue;
		ans += a[i] - now;
	}
	//cout<<"When now = "<<now<<" , the ans = "<<ans<<endl;
	return ans;
}
void erfen(long long x, long long y)
{
	long long l = x;
	long long r = y;
	while(r > l)
	{
		long long mid = (l + r) >> 1;
		long long fev = holl(mid);
		if(fev < m)
		{
			r = mid - 1;
			continue;
		}
		if(fev == m)
		{
			cout<<mid;
			return;
		}
		if(fev > m)
		{
			if(holl(mid + 1) < m)
			{
				cout<<mid;
				return;
			}
		}
		l = mid + 1;
	}
}
int main()
{
	cin>>n>>m;
	long long max_high = 0;
	for(long long i = 1;i <= n;i++)
	{
		cin>>a[i];
		if(a[i] > max_high) max_high = a[i];
	}
	erfen(0, max_high);
	return 0;
}

这是我第二次提交的代码,100100


#include<bits/stdc++.h>
using namespace std;
long long n,m;
long long a[1000005];
long long holl(long long now)
{
	long long ans = 0;
	for(long long i = 1;i <= n;i++)
	{
		if(now >= a[i])continue;
		ans += a[i] - now;
	}
	//cout<<"When now = "<<now<<" , the ans = "<<ans<<endl;
	return ans;
}
void erfen(long long x, long long y)
{
	long long l = x;
	long long r = y;
	while(r > l)
	{
		long long mid = (l + r) >> 1;
		long long fev = holl(mid);
		if(fev < m)
		{
			r = mid - 1;
			continue;
		}
		if(fev == m)
		{
			cout<<mid;
			return;
		}
		if(fev > m)
		{
			if(holl(mid + 1) < m)
			{
				cout<<mid;
				return;
			}
		}
		l = mid + 1;
	}
}
int main()
{
	cin>>n>>m;
	long long max_high = 0;
	for(long long i = 1;i <= n;i++)
	{
		cin>>a[i];
		if(a[i] > max_high) max_high = a[i];
	}
	erfen(0, max_high);
	return 0;
}

然而,改动了范围-↓

改变前改变后
l=mid+1l = mid +1l=mid1 l = mid - 1
r=mid1 r = mid - 1r=mid+1 r = mid + 1
就变成了100100分,但是这个题目的 HH的数据类型是整数啊?
2021/7/29 22:03
加载中...