求助,第13个点为什么过不去

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

star_magic_young @ 2018-03-04 19:38:00

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
long long n,m,s;
long long ans;
long long v[200010][2],l=0,r,mid,q[200010][2];
long long x[200010],ss[200010];
int main()
{
    scanf("%lld%lld%lld",&n,&m,&s);
    ans=s<<10;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld",&v[i][0],&v[i][1]);
        r=max(r,v[i][0]);
    }
    long long rr=r;
    for(int i=1;i<=m;i++)
        scanf("%lld%lld",&q[i][0],&q[i][1]);
    while(l<r-1)
    {
        mid=(l+r)/2;
        //cout<<mid<<endl;
        for(int i=1;i<=n;i++)
        {
            if(v[i][0]>=mid)
            {
                x[i]=x[i-1]+1;
                ss[i]=ss[i-1]+v[i][1];
            }
            else
            {
                x[i]=x[i-1];
                ss[i]=ss[i-1];
            }
        }
        /*for(int i=1;i<=n;i++) cout<<x[i]<<" ";
            cout<<endl;
        for(int i=1;i<=n;i++) cout<<ss[i]<<" ";
            cout<<endl;*/
        long long xs=0;
        for(int i=1;i<=m;i++)
            xs+=(x[q[i][1]]-x[q[i][0]-1])*(ss[q[i][1]]-ss[q[i][0]-1]);
        //cout<<xs<<endl;
            ans=min(ans,abs(s-xs));
        if(s-xs<1LL*0) l=mid;
        else r=mid;
    }
    l=max(1LL*0,l-2);r=min(rr,r-2);
    for(;l<=r;l++)
    {
        for(int i=1;i<=n;i++)
        {
            if(v[i][0]>=l)
            {
                x[i]=x[i-1]+1;
                ss[i]=ss[i-1]+v[i][1];
            }
            else
            {
                x[i]=x[i-1];
                ss[i]=ss[i-1];
            }
        }
        long long xs=0;
        for(int i=1;i<=m;i++)
            xs+=(x[q[i][1]]-x[q[i][0]-1])*(ss[q[i][1]]-ss[q[i][0]-1]);
        ans=min(ans,abs(s-xs));
    }
    printf("%lld",ans);
    return 0;
}

by 李不似 @ 2020-10-12 20:02:35

十三过不去加一


|