题解 P1314 【聪明的质监员】

木留木留木 · 2016-11-19 16:44:44 · 题解

记住输入输出要用scanf和printf不然就超时了……

把题目看懂之后就会想到二分，将标准值进行二分。

然而还有区间……

就可以用前缀和啦！

总之是各种优化嘿嘿嘿

还考语文阅读能力x

···cpp

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
long long l[200010],r[200010],w[200010],v[200010],sum[200010],ss[200010];
long long n,m,s,le,ri,wmx=0,mid,mi;
void qhsum(long long ww) //前缀和，sum是符合条件的v之和 ，ss是个数 
{
    for(int i=1;i<=n;i++)  //预处理  
    {
        if(w[i]>=ww) ss[i]=ss[i-1]+1,sum[i]=sum[i-1]+v[i];  //传说中的前缀和~
        else ss[i]=ss[i-1],sum[i]=sum[i-1];
    }
}
long long check(long long lw)
{
    long long y=0,t=0,g;
    memset(sum,0,sizeof(sum));
    memset(ss,0,sizeof(ss));
    qhsum(lw);
    for (int i=1;i<=m;i++)
    {
        y+=(ss[r[i]]-ss[l[i]-1])*(sum[r[i]]-sum[l[i]-1]);
    }
    return y;
}
int main()
{
    cin>>n>>m>>s;
    long long k=12425374554373ll,wmn=12425374554373ll;
    for (int i=1;i<=n;i++)
    {
        cin>>w[i]>>v[i];
        if (w[i]>wmx) wmx=w[i]; //输入 
        wmn=min(wmn,w[i]);
    }
    for (int i=1;i<=m;i++)
    cin>>l[i]>>r[i];
    le=wmn;ri=wmx;
    long long f;
    long long rmi=12425374554373ll;
    while (le<=ri)
    {
        mid=(le+ri)/2;
        f=check(mid);
        if (f>s) 
        {
            le=mid+1;
            k=min(k,f-s);
//            if (k>f-s) k=f-s; //取较小者 
        }
        else if (f<s)
        {
            ri=mid-1;
            k=min(k,s-f);
//            if (k>s-f) k=s-f; //同上 
        }
        else 
        {
            k=0;
            break;
        }
    }
    printf("%lld",k);
    return 0;
}
···