55分求助

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

无情。浪剑心 @ 2020-10-23 16:59:48

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,s;
ll rid,mid;
ll lef=0x3f3f3f3f3f3f3f3f;
ll cnt;
ll w[200005],v[200005];
ll a[200005],b[200005];  
ll now,cmp; 
ll sum[200005];
ll g[200005];
ll minn=0x3f3f3f3f3f3f3f3f;
bool check(int x)
{
    now=0; cmp=0;
    memset(sum,0,sizeof(sum)); memset(g,0,sizeof(g));
    for(int i=1;i<=n;i++)
    {
        if(w[i]>=x)
        {
            sum[i]=v[i]+sum[i-1]; g[i]=g[i-1]+1;
        }
        else 
        {
            sum[i]=sum[i-1]; g[i]=g[i-1];
        }
    }
    for(int i=1;i<=m;i++)
    {
        cmp+=(sum[b[i]]-sum[a[i]-1])*(g[b[i]]-g[a[i]-1]);
    }
    now=llabs(cmp-s);
    if(cmp>s) return true;
    else return false;  
}
int main()
{
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i]>>v[i];
        rid=max(rid,w[i]);
        lef=min(lef,w[i]);
    }
    for(int i=1;i<=m;i++)
    {
        cin>>a[i]>>b[i];
    } 
    lef--;rid+=2;
    while(lef<=rid)
    {
        mid=(lef+rid)/2;
        if(check(mid)==true) lef=mid+1;
        else rid=mid-1;
        if(minn>now) minn=now;
    }
    printf("%lld",now);
    return 0;
}

|