题解 P1314 【聪明的质监员】

半仙胡小桃 · 2017-08-07 20:56:06 · 题解

首先我们知道这道题目肯定是二分答案

但是我们每次都从区间枚举去找总值，显然不行

所以我们想到根据每个w值(因为区间有可能重叠)

每次处理两个数组，第一个去找区间可以满足矿的个数，另一个去找满足矿的总价值

这样找值的时候只有一层的m循环辣

#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
int v[200001],w[200001];
struct ss{
    int l;
    int r;
};
ss a[200001];
int cnt[200001];
long long vs[200001];
long long n,m,s;
int l,r;
long long check(int mid)
{
    for(int i=1;i<=n;i++)
     if(w[i]>=mid) cnt[i]=cnt[i-1]+1,vs[i]=vs[i-1]+v[i];
     else          cnt[i]=cnt[i-1],vs[i]=vs[i-1];
    long long ans=0;
    for(int i=1;i<=m;i++)
     {
         ans+=(cnt[a[i].r]-cnt[a[i].l-1])*(vs[a[i].r]-vs[a[i].l-1]);
     }
     return ans;
}
int main()
{
    //freopen("qc.in","r",stdin);
    //freopen("qc.out","w",stdout);
    scanf("%lld%lld%lld",&n,&m,&s);
    for(int i=1;i<=n;i++)
     scanf("%d%d",&w[i],&v[i]),r=max(r,w[i]);
    for(int i=1;i<=m;i++)
     scanf("%d%d",&a[i].l,&a[i].r);
    r++;
    long long ans=40000000000000;
    while(l<=r)
    {
       int mid=(l+r)>>1;
       long long d=check(mid);
       if(d<s)
        r=mid-1;
       if(d>s) 
        l=mid+1;
       if(d==s) {printf("0\n");return 0;}
       long long dis=s-d;
       if(dis<0) dis=-dis;
       ans=min(ans,dis);
    }
     printf("%lld",ans);
     //fclose(stdin);
     //fclose(stdout);
     return 0;
}