[NOIP2011 提高组] 聪明的质监员

原题链接

首先要读懂题目啊 ：[Wj>=W] 其实是一种bool表达，即大于等于时取1，小于时取0，然后再进行求和。

根据要求出 最小值 大概可以猜测要运用二分，那么我们来判断单调性，首先W在所有矿石的最大最小值之间取值，W越小Y越大，W越大Y越小（观察和推理都很容易得到），那么Y是符合单调性的，即可以运用二分。

而题目又给出了m个区间，如果都一个区间一个区间的遍历时间复杂度就是O（n*m*logv）肯定会超时，那么就很容易联想到前缀和将复杂度变为O（（n+m）logv）。

所以这题考察的就是 二分+前缀和 ，外加一些阅读理解

在这里我是对W进行二分然后求出对应的Y去跟s比较从而缩小区间。

主要代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int w[N],v[N],w2[N],l[N],r[N];
ll s,v2[N];
int n,m;
ll check(int W){
    memset(w2,0,sizeof(w2));
    memset(v2,0,sizeof(v2));
    for (int i=1;i<=n;i++){
        if (w[i]>=W){    //对w，v数组进行预处理
            w2[i]=1;
            v2[i]=v[i];
        }
        w2[i]+=w2[i-1];   //进行前缀和
        v2[i]+=v2[i-1];
    }
    ll sum=0;
    for (int i=1;i<=m;i++)
        sum+=(w2[r[i]]-w2[l[i]-1])*(v2[r[i]]-v2[l[i]-1]);  //累加求值
    return sum;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m>>s;
    int min_=1e6+5,max_=0;
    for (int i=1;i<=n;i++){
        cin>>w[i]>>v[i];
        min_=min(min_,w[i]);
        max_=max(max_,w[i]);
    }
    for (int i=1;i<=m;i++) cin>>l[i]>>r[i];
    int left=min_-1,right=max_+1;   //理论上check（left）>s   check(right)<=s 但是也可能无论怎么取都取不到W使得check（W）>s
    while (left+1<right){   //对W进行二分
        int mid=left+(right-left>>1);
        if (check(mid)>s) left=mid;   
        else right=mid;
    }
    ll cnt;
    cnt=min(abs(s-check(right)),abs(s-check(left)));
    cout<<cnt;
    return 0;
}