社区讨论
求助!!!
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 条回复,欢迎继续交流。
正在加载回复...