wmq2006 @ 2020-07-25 08:56:37
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<cstring>
#include<string>
#include<cstdio>
using namespace std;
int w[300001],v[300001],l[300001],r[300001],n,m,s,cnt=0;
long long qw[200001]={0},qv[200001]={0};
long long ans=1e15,answ=0;
long long u=0,d=1e15,mid;
long long check(int k){
long long cnt=0;
for(int i=1;i<=n;i++)qw[i]=0,qv[i]=0;
for(int i=1;i<=n;i++){
if(w[i]>=k){
qw[i]=qw[i-1]+1;
qv[i]=qv[i-1]+v[i];
}
else{
qw[i]=qw[i-1];
qv[i]=qv[i-1];
}
}
for(int i=1;i<=m;i++)cnt+=(qv[r[i]]-qv[l[i]-1])*(qw[r[i]]-qw[l[i]-1]);
return cnt;
}
int main(){
//freopen("qc.in","r",stdin);
//freopen("qc.out","w",stdout);
cin>>n>>m>>s;
for(int i=1;i<=n;i++){
cin>>w[i]>>v[i];
//u=max(u,w[i]);
//d=min(d,w[i]);
}
u=1e6;
d=0;
for(int i=1;i<=m;i++)cin>>l[i]>>r[i];
while(d<u){
mid=(u+d)/2;
//cout<<mid<<" "<<check(mid)<<endl;
if(check(mid)<s)u=mid-1;
if(check(mid)>s)d=mid+1;
if(abs(check(mid)-s)<ans)ans=abs(check(mid)-s);
if(check(mid)==s){cout<<ans<<endl;return 0;}
}
cout<<ans<<endl;
return 0;
}只要n,m大于1000就无法输入，我的电脑上只有Linux，哪位好心人有DEV-C++帮我看一下在CEV编译器里能不能正常输入
另外能不能帮我看看这个题为什么输入不了，真的，感觉题真的不难，看看自己代码的思路也和题解的差不多
by ducati @ 2020-07-25 09:00:19
把数组先开小点
by ducati @ 2020-07-25 09:00:35
提交的时候再开大；或者直接上在线IDE搞事情
by wmq2006 @ 2020-07-25 09:02:00
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<cstring>
#include<string>
#include<cstdio>
using namespace std;
int w[200001],v[200001],l[200001],r[200001],n,m,s,cnt=0;
long long qw[200001]={0},qv[200001]={0};
long long ans=1e15,answ=0;
long long u=0,d=1e15,mid;
long long check(int k){
long long cnt=0;
for(int i=1;i<=n;i++)qw[i]=0,qv[i]=0;
for(int i=1;i<=n;i++){
if(w[i]>=k){
qw[i]=qw[i-1]+1;
qv[i]=qv[i-1]+v[i];
}
else{
qw[i]=qw[i-1];
qv[i]=qv[i-1];
}
}
for(int i=1;i<=m;i++)cnt+=(qv[r[i]]-qv[l[i]-1])*(qw[r[i]]-qw[l[i]-1]);
return cnt;
}
int main(){
//freopen("qc.in","r",stdin);
//freopen("qc.out","w",stdout);
cin>>n>>m>>s;
for(int i=1;i<=n;i++){
cin>>w[i]>>v[i];
//u=max(u,w[i]);
//d=min(d,w[i]);
}
u=1e6;
d=0;
for(int i=1;i<=m;i++)cin>>l[i]>>r[i];
while(d<u){
mid=(u+d)/2;
//cout<<mid<<" "<<check(mid)<<endl;
if(check(mid)<s)u=mid-1;
if(check(mid)>s)d=mid+1;
if(abs(check(mid)-s)<ans)ans=abs(check(mid)-s);
if(check(mid)==s){cout<<ans<<endl;return 0;}
}
cout<<ans<<endl;
return 0;
}新版代码：数组变小，还是无法输入
by ducati @ 2020-07-25 09:02:17
再变小点
by wmq2006 @ 2020-07-25 09:02:18
@ducati 线上IDE显示输入长度不合法
by ducati @ 2020-07-25 09:02:28
实在不行有在线IDE啊QAQ
by ducati @ 2020-07-25 09:02:55
对不起，我实在帮不了您了 %%%
by ducati @ 2020-07-25 09:03:04
提交试试看，万一AC了呢
by wmq2006 @ 2020-07-25 09:03:30
@ducati 提交了七八遍，显示输出乱码
by wmq2006 @ 2020-07-25 09:04:06
@ducati LINUX LGIDE都试了，都不行，就不知道为什么，写过这么多程序就这个莫名其妙