题解 P1314 【聪明的质监员】

n0000000000o · 2018-07-20 17:13:00 · 题解

P1314 聪明的质监员

分析：

对于每一个 Y_i ，有
且 w_j W ，j为矿石编号
即区间 [L_i ,R_i] 中所有 w_j\geq W 的石块都选， 在区间 [L_i ,R_i] 内

即求 abs(s - Y) 的最小值
考虑二分查找枚举答案 w
通过 Y(w) - s 判断二分的区间
编写 Y(w) 时，因为存在多次区间询问，考虑用前缀和降低复杂度

代码实现

#include <bits/stdc++.h>
using namespace std;
/*单调性说明: 
    W上升 ，  每一个 Yi 中 两项都下降， Yi下降，   所以总的 Y 也一定下降 ，单调下降（其实是不上升） 
*/
int erfen(int l, int r);
long long Y (int x);
long long findnum(int l, int r);
long long findsum(int l, int r);
long long n, m, s;
long long numm[200000 + 9], summ[200000 + 9], v[200000 + 9], w[200000 + 9];//numm[] summ[] 记录区间i j 大于W的个数以及和  前缀和 
int ll[200000 + 9], rr[200000 + 9];
long long read();
int main()
{
    long long maxw = 0;
    cin >> n >> m >> s;
    for (int i = 1; i <= n; i++)
    {
        w[i]=read();
        v[i]=read();
        maxw = max(maxw, w[i]);//记录下最大重量以此为二分上边界 
    }
    for (int i = 1; i <= m; i++)
    {
        ll[i] = read();
        rr[i] = read();
    }
    int w = erfen(0, maxw);
    cout << min ( Y(w) - s, s - Y(w+1) );//见下    ↓↓↓↓↓↓ 
    return 0;
} 
long long read()//快读 
{
    long long x=0;
    char c=getchar();
    while(c>'9'||c<'0') 
        c=getchar();
    while(c<='9'&&c>='0') 
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
int erfen (int l, int r)//找使  Y-S >=0 的最接近的W 此时 的答案在 W与 W+1 之间 （因为要求绝对值） 
{
    if (l == r)
        return l;
    int mid = ((l+r+1)>>1);
    if (Y(mid) >= s) 
        return erfen (mid, r);
    else
        return erfen (l ,mid - 1); 
}
long long Y (int x)
{
    long long y = 0;
    for (int i = 1; i <= n; i++)//初始化 
    {   
        numm[i] = numm[i-1] ;
        summ[i] = summ[i-1] ;
        if(w[i] >= x)   //满足条件 ，前缀和增加 
        {   
            numm[i] += 1;
            summ[i] += v[i];
        }   
    }
    for (int i = 1; i <= m; i++)
    {
        int l = ll[i];
        int r = rr[i];
        y += (numm[r] - numm[l-1])* (summ[r] - summ[l-1]);
    }
    return y;
}