题目传送门

讲真,既然质监员这么聪明,为什么要让我们帮他设计程序?

其实,我最想说的,不是这个题,而是这个\(\Sigma\)

这个题的式子是这样的:
Noip2011提高组 聪明的质监员-LMLPHP

嗯,它的意思是:在\(L_i\)到\(R_i\)这段区间里,合法的矿石的数量\(\times\)合法矿石的总价值

接下来就是这道题的思路了,知道这道题是二分后,这道题还是挺简单的,注意一下\(\tt{long\;long}\)的细节就可以了

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
ll read(){
    ll k=0; char c=getchar();
    for(;c<'0'||c>'9';) c=getchar();
    for(;c>='0'&&c<='9';c=getchar())
      k=(k<<3)+(k<<1)+c-48;
    return k;
}
ll sum[200010],ans=999999999999999999LL;
int cnt[200010],v[200010],w[200010],l[200010],r[200010];
int h=100000000,t;
int main(){
    int n=read(),m=read(); ll s=read();
    for(int i=1;i<=n;i++)
        w[i]=read(),v[i]=read(),h=min(w[i],h),t=max(w[i],t);
    for(int i=1;i<=m;i++)
        l[i]=read(), r[i]=read();
    h--, t++;
    while(h<t){
        int mid=(h+t)>>1;
        for(int i=1;i<=n;i++){
            cnt[i]=cnt[i-1]; sum[i]=sum[i-1];
            if(w[i]>=mid) cnt[i]++,sum[i]+=v[i];
        }
        ll y=0;
        for(int i=1;i<=m;i++){
            y+=(cnt[r[i]]-cnt[l[i]-1])*(sum[r[i]]-sum[l[i]-1]);
        }
        y=s-y;
        if(llabs(y)<ans) ans=llabs(y);
        if(y<=0) h=mid+1;
        else t=mid;
    }
    cout<<ans;

    return 0;
}
05-27 16:31