站外题求助
查看原帖
站外题求助
699471
yuxiaoyu20090104楼主2023/5/10 00:01

90分,想知道我代码哪里有问题,代码如下

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m;
ll sum[100005];
ll Max,ans;
int Bin(ll x,int now)
{
	int l=now+1,r=n+1;
	while(l+1<r)
	{
		int mid=(l+r)>>1;
		if(sum[mid]-sum[now]<=x)l=mid;
		else r=mid;
	}
	return l;
}
bool check(ll x)
{
	int now=0,cnt=0;
	while(now<n)
	{
		int p=Bin(x,now);
		if(sum[p]-sum[now]>Max)Max=sum[p]-sum[now];
		now=p;
		//cout<<now<<" "<<x<<endl;
		cnt++;
	}
	//cout<<cnt<<endl;
	if(cnt<=m)
	{
		ans=Max;
		return 1;
	}
	return 0;
}
int main()
{
	//freopen("expense.in","r",stdin);
	//freopen("expense.out","w",stdout);
	cin>>n>>m;
	ll temp=0;
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		sum[i]=sum[i-1]+x;
		if(x>temp)temp=x;
	}
   ans=temp//当n=1
	ll L=temp-1,R=sum[n];
	while(L+1<R)
	{
		ll mid=(L+R)>>1;
		if(!check(mid))L=mid;
		else R=ans;
		Max=0;
	}
	cout<<ans;
	return 0;
}
2023/5/10 00:01
加载中...