【NOIP 2011 提高组 Day2】聪明的质监员

题目

---

题解

–这道题吧，就是题目中求Yi的公式很恶心罢了
宝宝来翻译一下，就是在 [Li,Ri] 的区间中，所有满足 wj>W 的矿石的数量 * 他们的价值之和
–这样就简单了，只需要二分查找一下就好（加上前缀和优化）
对于一个mid，发现：
1. 如果Y>S，说明入选的矿石多了，应把mid调大，即L=mid+1
2. 如果Y

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=200005;

int n,m;
long long s;
int w[MAXN],v[MAXN];
int l[MAXN],r[MAXN];
int L=0x3f3f3f3f,R;
long long vs[MAXN],ss[MAXN];
long long ans=0x7f7f7f7f7f;


int main(){
//  freopen("qc.in","r",stdin);
//  freopen("qc.out","w",stdout);
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&w[i],&v[i]);
        L=min(L,w[i]);
        R=max(R,w[i]);
    }
    for(int i=1;i<=m;i++)
        scanf("%d%d",&l[i],&r[i]);
    L=L-1;
    R=R+2;
    while(L<=R){
        long long W=(L+R)/2;
        memset(vs,0,sizeof(vs));
        memset(ss,0,sizeof(ss));
        for(int i=1;i<=n;i++){
            vs[i]=vs[i-1];
            ss[i]=ss[i-1];
            if(w[i]>=W){
                vs[i]+=v[i];
                ss[i]+=1;
            }
        }
        long long Y=0;
        for(int i=1;i<=m;i++)
            Y+=(ss[r[i]]-ss[l[i]-1])*(vs[r[i]]-vs[l[i]-1]);
        if(Y>s)
            L=W+1;
        else
            R=W-1;
        if(abs(Y-s)<ans)
            ans=abs(Y-s);
    }
    cout<<ans;
    return 0;
}