NOIP2011 提高组 聪明的质监员（二分+前缀和）

看到这道题，应该都能想到用二分，那问题是怎么去判定呢？

我们考虑用前缀和（a1统计w，a2统计v），枚举每个矿石，，当前判定的值是x，如果该矿石的w>=x，a1[i]=a1[i-1]+1,a2[i]=a2[i-1]+v[i]；反之直接等于上一个就行了。

枚举完后，按照题目给的公式，更新它与s差值绝对值的最小值，得到最终答案。

#include<bits/stdc++.h>

typedef long long LL;

using namespace std;

const int N=2e5+10;

int n,m;

LL s,sum,ans=0x3f3f3f3f3f3f3f3f,qzh1[N],qzh2[N];

struct node{

    int w,v;

}a[N];

struct ask{

    int l,r;

}q[N];

bool check(int x){

    LL res=0;sum=0;

    memset(qzh1,0,sizeof(qzh1));

    memset(qzh2,0,sizeof(qzh2));

    for(int i=1;i<=n;i++){

        if(a[i].w>=x){

            qzh1[i]=qzh1[i-1]+1;

            qzh2[i]=qzh2[i-1]+a[i].v;

        }

        else{

            qzh1[i]=qzh1[i-1];

            qzh2[i]=qzh2[i-1];

        }

    }

    for(int i=1;i<=m;i++){

        res+=(qzh1[q[i].r]-qzh1[q[i].l-1])*(qzh2[q[i].r]-qzh2[q[i].l-1]);

    }

    sum=llabs(res-s);

    if(res>s) return true;

    else return false;

}

int main(){

    scanf("%d%d%lld",&n,&m,&s);

    for(int i=1;i<=n;i++)

        scanf("%d%d",&a[i].w,&a[i].v);

    int h=0,t=1e6;

    for(int i=1;i<=m;i++)

        scanf("%d%d",&q[i].l,&q[i].r);

    while(h<=t){//二分答案

        int mid=h+t>>1;

        if(check(mid)) h=mid+1;

        else t=mid-1;

        if(sum<ans) ans=sum;//更新答案

    }

    cout<<ans;

}

看到有区间，不一定要用数据结构去维护，有可能前缀和更简单些。

NOIP2011 提高组 聪明的质监员（二分+前缀和）的相关教程结束。