跪求错啊啊啊啊!

P1314 [NOIP2011 提高组] 聪明的质监员

Gadfly @ 2018-08-03 21:15:20

首先,本蒟的代码是借鉴了题解的

but不晓得是什么回事QWQ,只有65(一片红~)

哪位大佬帮忙看看

#include<iostream>
#include<cstring>
#include<algorithm>
#define R register
#define F(i,a,b) for(R int i=a;i<=b;i++)
#define M 200010
using namespace std;
typedef long long ll; 
int w[M],v[M],LL[M],rr[M];
int n,m;
ll s,SUM,ans=0x7fffffff;
ll qs[M],qc[M];
inline int min(int a,int b){return a<b?a:b;}
inline int max(int a,int b){return a>b?a:b;}
bool check(int k)
{
     SUM=0;
     //F(i,0,n+1){q[i].c=0; q[i].sum=0;}
     memset(qc,0,sizeof(qc));
     memset(qs,0,sizeof(qs));
     F(i,1,n)
     {
        if(w[i]>=k) {qc[i]=qc[i-1]+1; qs[i]=qs[i-1]+v[i];}
        else {qc[i]=qc[i-1]; qs[i]=qs[i-1];}
     }
     F(i,1,m)
     {
        SUM+=(qc[rr[i]]-qc[LL[i]-1])*(qs[rr[i]]-qs[LL[i]-1]);//∑ 
     }
     return SUM>=s;
}
int main()
{
    int l=0x7fffffff,r=-1;
    //ios::sync_with_stdio(false);
    scanf("%d%d%lld",&n,&m,&s);
    //cout<<n<<" "<<m<<" "<<s<<endl;
    F(i,1,n) {scanf("%d%d",&w[i],&v[i]); r=max(r,w[i]); l=min(l,w[i]);}
    F(i,1,m) scanf("%d%d",&LL[i],&rr[i]);
    l--; r++;//判断全部都选和全部都不选的情况 
    //cout<<l<<" "<<r<<endl;
    int mid=(l+r)>>1;
    while(l<=r)
    {
        if(check(mid)) l=mid+1;
        else r=mid-1; 
        mid=(l+r)>>1;
        ans=min(ans,llabs(SUM-s)); 
    }
    printf("%lld",ans);
    return 0;
}

by edjzy @ 2018-08-04 00:17:31

@龘靐齉齾麤 what


上一页 |