题解 P1314 【聪明的质监员】

荣一鸣 · 2018-06-18 13:49:13 · 题解

这道题可以看出来是一道二分题（没错一下就看出来了），因为你的Y随着变量w的变化时有序的，即w递增时Y递减。

while(wn<=wx){
    int mid=(wn+wx)>>1;
    if(check(mid)){
        wn=mid+1;
    }
    else{
        wx=mid-1;
    }
    ans=min(ans,abs(Y-S));
}

然后再结合前缀和的技巧就能减少求和的时间

for(int i=1;i<=n;i++){
    sumv[i]=sumv[i-1];
    sumn[i]=sumn[i-1];
    if(w[i]>=wm){
        sumv[i]+=v[i];
        sumn[i]+=1;
    }
}

注意数据大小，使用long long 下面是总代码

#include<stdio.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
long long m,n,S,Y;
int w[200010],v[200010];
vector<int> ww;
int st;
int lt[200010],rt[200010];
long long sumn[200010],sumv[200010];
int wn=100000000,wx=0;

bool check(int wm){
    Y=0;
    memset(sumv,0,sizeof(sumv));
    memset(sumn,0,sizeof(sumn));
    for(int i=1;i<=n;i++){
        sumv[i]=sumv[i-1];
        sumn[i]=sumn[i-1];
        if(w[i]>=wm){
            sumv[i]+=v[i];
            sumn[i]+=1;
        }
    }
    for(int i=1;i<=m;i++){
        long long sum;
        sum=(sumv[rt[i]]-sumv[lt[i]-1])*(sumn[rt[i]]-sumn[lt[i]-1]);
        Y+=sum;
    }
    if(Y>S) return true;
    else return false;
}

int main(){
    cin>>n>>m>>S;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&w[i],&v[i]);
        wn=min(wn,w[i]);
        wx=max(wx,w[i]);
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d",&lt[i],&rt[i]);
    }
    long long ans=0x7fffffffffff;
    while(wn<=wx){
        int mid=(wn+wx)>>1;
        if(check(mid)){
            wn=mid+1;
        }
        else{
            wx=mid-1;
        }
        ans=min(ans,abs(Y-S));
    }
    cout<<ans;
    return 0;
}