题解 P1314 【聪明的质监员】

· · 题解

首先题面一定要看懂，看清（上次我就是没有看懂）。说白了，就是使W取一个最合适的值，使每一个所给区间内满足条件的矿石的数量乘上价值之和，最后计算总和使与S最近。

我们根据分值分布来分析算法：

1、30分算法：O（n^3），首先O（n）进行W值选取的枚举，然后O（n^2）判断+计算；

2、50分算法：O（n^2 log n）。根据每次选取W值我们易发现，所得的总值是一个单调函数，随W增大而减小，且一定存在零点。故为了求得最小值，我们需要得到零点位于那两个整数之间。这样用二分显然比枚举快。O（log n）的二分加上O（n^2）的判断+计算；

3、100分算法：200000的数据显然只能O（n log n）或者O（n）了，但是这道题O（n）很明显不现实。我们的任务在于，如何消去O（n^2）这么大的判断与计算？这里，可以采取前缀和优化——由于每次计算检验值之和的时候，W值固定，故可以用O（n）的时间扫描一遍，用a[i]表示前i个矿石满足条件的个数；b[i]表示前i个满足条件的矿石价值之和。故每次询问一个区间的时候，可以O（1）直接相减！这样，复杂度就降到了O（n log n）。（这其实是一个很简单的优化但是我想了很久，看来姿势不够）

4、（这个可以无视）70分算法：存在这个分数段就必然存在这种算法对吧。。。这一定是给那些用了前缀和却没有用二分的。。。虽然我觉得很不可思议。

还有一个很重要的数据范围——权值会爆INT。

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
long long n,m,max1,min1,l,r,mid;
long long s,ss[200010],sum[200010];
long long w[200010],v[200010],a[200010],b[200010];
inline long long read()
{
    long long data=0,w=1;
    char ch=0;
    while (ch!='-' && (ch<'0' || ch>'9')) ch=getchar();
    if (ch=='-') {
        w=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9') {
        data=data*10+ch-'0';
        ch=getchar();
    }
    return data*w;
}
long long ok(int W)
{
    long long y=0,t=0;
    for (int i=1;i<=n;++i) {
        ss[i]=0;
        sum[i]=0;
    }
    for (int i=1;i<=n;++i) {
        if (w[i]>=W) {
            ss[i]=ss[i-1]+1;
            sum[i]=sum[i-1]+v[i];
        }
        else {
            ss[i]=ss[i-1];
            sum[i]=sum[i-1];
        }
    }
    for (int i=1;i<=m;++i) {
        y=y+(ss[b[i]]-ss[a[i]-1])*(sum[b[i]]-sum[a[i]-1]);
    }
    return y;
}
int main()
{
    //freopen("zjy.in","r",stdin);
    //freopen("zjy.out","w",stdout);
    n=read();
    m=read();
    s=read();
    max1=0;
    min1=12425374554373ll;
    for (int i=1;i<=n;++i) {
        w[i]=read();
        v[i]=read();
        if (max1<w[i]) max1=w[i];
        if (min1>w[i]) min1=w[i];
    }
    for (int i=1;i<=m;++i) {
        a[i]=read();
        b[i]=read();
    }
    l=min1;
    r=max1;
    long long ans=12425374554373ll,ans1;
    while (l<=r) {
        mid=(l+r)/2;
        ans1=ok(mid);
        if (ans1>s) {
            l=mid+1;
            if (ans>ans1-s) ans=ans1-s;
        }
        else if (ans1<s) {
            r=mid-1;
            if (ans>s-ans1) ans=s-ans1;
        }
        else {
            ans=0;
            break;
        }
    }
    cout<<ans<<endl;
    return 0;
}