题解 P1314 【聪明的质监员】

AtlasDelRey · 2017-09-28 16:39:13 · 题解

二分答案就可以了。二分所取的w，这里记作ww，记录w[]中min和max，在[min-1,max+1]这个区间二分（一个都不合法或者全部合法），在check()中扫一遍w[]，用前缀和记录合法个数（sum[][0]）和价值和（sum[][1]），(sum[r[i]][0]-sum[l[i]-1][0])*(sum[r[i]][1]-sum[l[i]-1][1])就是此时的Yi，这里记作summ，如果summ>s说明ww过小，summ<0说明ww过大。

···cpp

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
long long ans=1e18,n,m,s,w[200002],v[200002],maxx,minn=1e9,l[200002],r[200002],sum[200002][2];
long long abss(long long a)
{
    return a>0?a:(-a);
}
void check(long long ll,long long rr)
{
    long long ww=(ll+rr)/2,summ=0;
    memset(sum,0,sizeof(sum));
    for(int i=1;i<=n;i++)
    {
        if(w[i]>=ww)sum[i][0]=sum[i-1][0]+1,sum[i][1]=sum[i-1][1]+v[i];
        else sum[i][0]=sum[i-1][0],sum[i][1]=sum[i-1][1];
    }
    for(int i=1;i<=m;i++)
    {
        summ+=(sum[r[i]][0]-sum[l[i]-1][0])*(sum[r[i]][1]-sum[l[i]-1][1]);
    }
    ans=min(abss(summ-s),ans);
    if(ll>=rr)return;
    if(summ==s){
        ans=0;
        return;
    }
//    if(ll==ww)return;
    if(summ>s)check(ww+1,rr);
    else check(ll,ww-1); 
}
int main()
{
    scanf("%lld%lld%lld",&n,&m,&s);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld",&w[i],&v[i]);
        maxx=max(w[i],maxx);
        minn=min(w[i],minn);
    }
    for(int i=1;i<=m;i++)
    scanf("%lld%lld",&l[i],&r[i]);
    check(minn-1,maxx+1);
    cout<<ans;
}
···