社区讨论

求助!!!

P1314[NOIP 2011 提高组] 聪明的质监员参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lo3eqqsl
此快照首次捕获于
2023/10/24 05:26
2 年前
此快照最后确认于
2023/10/24 05:26
2 年前
查看原帖
C
#include<bits/stdc++.h>
using namespace std;
long long n,m,s;
long long l[200005],r[200005];
long long w[200005],v[200005];
long long ans=0x3f3f3f3f3f3f3f3f;//终究是不够大 
long long bks,rxy,sumn;
long long maxn=-1,minn=2147483647;
long long q_st[200005],q_ed[200005]; 
int check(int base)
{
	int c1=0,c2=0;
	rxy=0,sumn=0;
	memset(q_st,0,sizeof(q_st));
	memset(q_ed,0,sizeof(q_ed));
	for(int i=1;i<=n;i++)
	{
		if(w[i]>=base)
		{
			q_st[i]=q_st[i-1]+1;
			q_ed[i]=q_ed[i-1]+v[i];
		}
		else
		{
			q_st[i]=q_st[i-1];
			q_ed[i]=q_ed[i-1];
		}
	} 
	
	for(int i=1;i<=m;i++)
	{
		c1=q_st[r[i]]-q_st[l[i]-1];
		c2=q_ed[r[i]]-q_ed[l[i]-1];
		sumn+=c1*c2;
	}
	
	
	rxy=llabs(sumn-s);//long long の abs 
	if(sumn>s)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}
 
 
 
 
int main()
{
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&w[i]);
		scanf("%lld",&v[i]);
		minn=min(minn,w[i]);
		maxn=max(maxn,w[i]);
	}
	
	minn=minn-1;
	maxn=maxn+1;//保个险...
	 
	for(int i=1;i<=m;i++)
	{
		scanf("%lld",&l[i]);
		scanf("%lld",&r[i]);
	}
	
	int zuo=minn,you=maxn;
	int mid;
	while(zuo<=you)
	{
		mid=(zuo+you)/2;
		if(check(mid))
		{
			//ans=rxy;
			zuo=mid+1;			
		}
		else
		{
			you=mid-1;
		}
		if(rxy<ans)
		{
			ans=rxy; //择最优 
		}
	}
	cout<<ans;
	return 0;
} 

为啥错了第6个点和第20个点QAQ






















回复

1 条回复,欢迎继续交流。

正在加载回复...