题解 P1314 【聪明的质监员】

SSHhh · 2018-10-27 22:22:53 · 题解

说实话，这题其实应该放到普及+/提高。思路其实就是简单的快速查找（其实你用二分或三分均可）+前缀和。

首先我们分析一下题面的式子，其实 Y_i 就等于该区间内大于等于 W 的数字数量与大于等于 W 的数字之和的乘积。也就是说，我们需要将重量排序后快速查找出一个与 S 的答案差距最小的地方。

那么，差距最小？肯定第一个想到的就是三分。所以我们的做法就出来了（下面附上思路）：

sort();
三分枚举()
{
    if(左中点的答案<右中点的答案)   左端点=左中点;
    else    右端点=右中点;
}

那么我们就到了第二个问题：计算对于每一个 w_i 的答案。如果每一个区间都去枚举复杂度是 n^2，肯定会 TLE 。所以我们就需要在 O(n) 的时间内处理出每一个 [L_i,R_i] 的答案。

既然需要求的是每一个区间的答案，那么第二个算法就出来了：前缀和。我们只需要枚举每一位上的东西，然后用前缀和扫一遍统计即可。这样单次计算复杂度就降到了O(n)。

最后如果三分没有枚举完，手动枚举剩下的那一点即可。

下面附上代码：

#include<iostream>
#include<algorithm>
#define N 1000005
#define abs(a) ((a)<0?-(a):(a))
#define INF 9999999999999999ll
using namespace std;
long long ans=INF,n,m,S,w[N],v[N],l[N],r[N],sum[N],sum2[N],q[N];
long long check(int W)
{
    long long now=0;
    for(int i=1;i<=n;i++)
    {
        sum[i]=sum[i-1],sum2[i]=sum2[i-1];
        if(w[i]>=W) sum[i]+=v[i],sum2[i]++;
    }
    for(int i=1;i<=m;i++)
        now+=(long long)(sum2[r[i]]-sum2[l[i]-1])*(sum[r[i]]-sum[l[i]-1]);
    return abs(now-S);
}
int main()
{
    cin>>n>>m>>S;q[0]=-1;
    for(int i=1;i<=n;i++)
        cin>>w[i]>>v[i],q[i]=w[i];
    for(int i=1;i<=m;i++)
        cin>>l[i]>>r[i];
    sort(q+1,q+n+1);
    int l=1,r=n;
    while(r>=l+4)
    {
        int mid=(l+r)/2,mid2=(r+mid)/2;
        if(check(q[mid])>check(q[mid2]))    l=mid;
        else    r=mid2;
    }
    for(int i=l;i<=r;i++)
        if(check(q[i])<ans)
            ans=check(q[i]);
    cout<<ans;
    return 0;
}