求助巨佬!不知道哪一步错了(悲)的蒟蒻跪谢!
查看原帖
求助巨佬!不知道哪一步错了(悲)的蒟蒻跪谢!
751403
xzjxzjxzj楼主2023/8/21 23:46

这是蒟蒻不知道哪一步有问题的代码qwq

#include<bits/stdc++.h>

using namespace std;

int n,m;
long long s;
int l[20005],r[20005];
int w[20005],v[20005];
long long pre_w[20005],pre_v[20005];
int maxx=-1,minn=0xfffffff;
long long sum;

bool check(int W)
{
	long long Y=0;
	sum=0;
	memset(pre_w,0,sizeof(pre_w));//?
	memset(pre_v,0,sizeof(pre_v));
	for(int i=1;i<=n;i++)
	{
		if(w[i]>=W)
		{
			pre_w[i]=pre_w[i-1]+1;
			pre_v[i]=pre_v[i-1]+v[i];
		}
		else
		{
			pre_w[i]=pre_w[i-1];
			pre_v[i]=pre_v[i-1];
		}
	}
	
	for(int i=1;i<=m;i++)
	{
		Y+=(pre_w[r[i]]-pre_w[l[i-1]])*(pre_v[r[i]]-pre_v[l[i-1]]);
	}
	sum=llabs(Y-s);//?
	return Y>s;
}

int main()
{
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++)
	{
		cin>>w[i]>>v[i];
		maxx=max(maxx,w[i]);
		minn=min(minn,w[i]);
	}
	for(int i=1;i<=m;i++)
	{
		cin>>l[i]>>r[i];
	}
	
	int left=minn-1,right=maxx+2;
	long long ans=0x3f3f3f3f3f3f3f3f;
	while(left<=right)
	{
		int mid=(left+right)/2;
		if(check(mid))
		{
			left=mid+1;
		}
		else
		{
			right=mid-1;
		}
		ans=min(ans,sum);
	}
	cout<<ans<<endl;
	return 0;
}

希望巨佬可以看看,蒟蒻跪谢!

2023/8/21 23:46
加载中...