题解 P1314 【聪明的质监员】

· · 题解

这题反复做了好久才做出来，自以为还算有些心痛的见解（都是血的代价啊）

垃圾的我准备发表第一篇题解，不喜勿喷

主要是二分求解，在0到最大重量间二分答案，如果和标准的差==0就可以直接退出了

还有就是一个前缀和处理Y中的前面那个项 和后面那个项，对于每一次二分的答案都要处理一遍，

然后用jia（）求和得出，比较后进行下一次操作

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define LL long long
using namespace std;
inline LL read()
{
    LL kk=0,f=1;
    char cc=getchar();
    while('9'<cc||cc<'0')
    {
        if(cc=='-')f=-1;
        cc=getchar();
    }
    while('0'<=cc&&cc<='9')
    {
        kk=(kk<<1)+(kk<<3)+cc-'0';
        cc=getchar();
    }
    return kk*f;
}
LL start=0,tail,w[200002],v[200002],qu[200002][2],N,M,S;
LL sum[200002],sumv[200002];
LL myabs(LL a)//一定要自己写，因为cmath里的不支持 long long
{
    if(a<0)return -a;
    else return a;
}
LL mymax(LL a,LL b)
{
    if(a>b)return a;
    else return b;
} 
void work(LL mid)//单次处理每一个s 得到每一组y考虑其Y的值将其中y1，y2...用jia()加起来 
{
    sum[0]=0;sumv[0]=0; 
    for(int i=1;i<=N;++i)
    { 
            if(w[i]>=mid)
            {
                sum[i]=sum[i-1]+1;
                sumv[i]=sumv[i-1]+v[i];
            }
            else 
            {
                sum[i]=sum[i-1];
                sumv[i]=sumv[i-1];
            }
    }
}
LL jia(LL mid)
{
    LL jie=0;
    for(register int i=1;i<=M;++i)
    {
        jie+=(sum[qu[i][1]]-sum[qu[i][0]-1])*(sumv[qu[i][1]]-sumv[qu[i][0]-1]);//-1很重要，丫的检查了好久才检查出来 表示qu【i】【0】也入选 
    }
    return jie;
}
int main()
{
    N=read(),M=read(),S=read();
    for(register int i=1;i<=N;++i)
    {
        w[i]=read();v[i]=read();tail=mymax(tail,w[i]);
    }
    for(register int i=1;i<=M;++i)
    {
        qu[i][0]=read();qu[i][1]=read();//用qu[i][0]表示左，qu【i】【1】表示右
    }
    LL ans=9223372036854775807;
    while(start<=tail)
    {
        LL mid=(start+tail)/2;
        work(mid);
        LL s1=jia(mid);
        if(myabs(s1-S)<ans)ans=myabs(s1-S);
        if(ans==0)goto end;
        if(s1>S)start=mid+1;//如果选取的mid 使s1 过大则提高mid来降低s1 
        else tail=mid-1;
    }
    end:
        printf("%lld",ans);
        return 0;
}