洛谷P1314 聪明的质监员二分答案

题目描述

小T 是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有 n 个矿石，从 1到n 逐一编号，每个矿石都有自己的重量 wi 以及价值vi 。检验矿产的流程是：

1 、给定m个区间[Li,Ri]；

2 、选出一个参数W；

3 、对于一个区间[Li,Ri]，计算矿石在这个区间上的检验值Yi：

这批矿产的检验结果Y 为各个区间的检验值之和。即：Y1+Y2...+Ym

若这批矿产的检验结果与所给标准值SSS 相差太多，就需要再去检验另一批矿产。小T不想费时间去检验另一批矿产，所以他想通过调整参数W 的值，让检验结果尽可能的靠近标准值S，即使得S−Y 的绝对值最小。请你帮忙求出这个最小值。

输入输出格式

输入格式：

第一行包含三个整数n,m,S，分别表示矿石的个数、区间的个数和标准值。

接下来的n行，每行2个整数，中间用空格隔开，第i+1行表示iii号矿石的重量wi和价值vi。

接下来的m 行，表示区间，每行2个整数，中间用空格隔开，第i+n+1 行表示区间[Li,Ri]的两个端点Li 和Ri。注意：不同区间可能重合或相互重叠。

输出格式：

一个整数，表示所求的最小值。

输入输出样例

输入样例#1： 复制

输出样例#1： 复制

说明

【输入输出样例说明】

当W选4的时候，三个区间上检验值分别为20,5,0 ，这批矿产的检验结果为 25，此时与标准值S相差最小为10。

【数据范围】

对于 10%的数据，有 1≤n,m≤10；

对于 30%的数据，有 1≤n,m≤500 ；

对于 50%的数据，有 1≤n,m≤5,000；

对于70% 的数据，有 1≤n,m≤10,000 ；

对于100%的数据，有1≤n,m≤200,000,0<wi,vi≤106,0<S≤1012,1≤Li≤Ri≤n

解释：

这个题很明显的二分枚举，但是还有一个前缀和有点坑人。

这题题其实点不多，就两个关键点：

第一：二分的判断。

可以看到：在W取0时，所有的区间内的矿石都可以选上，

而在W大于最大的质量时，所有的矿石都选不上。

然后简单算一下就发现：

W越大，矿石选的越少，W越小，矿石选的越多。

所以，随着W增大，Y值减小；

所以：二分的判断条件出来了：

当Y>S 时，需要增大W来减小Y,从而|Y-s|变小；

当Y=s时，|Y-s|==0;

当Y<s时，需要减小W来增大Y,从而|Y-s|变大；

第二：前缀和。

我们在计算一个区间的和时（虽然这里是两个区间和再相乘，但没关系）

通常是用前缀和的方法来缩减时间，直接模拟是n^2的，而前缀和成了2*n

大大的优化了时间，前缀和不会的去先学前缀和，我默认大家都会，就不赘述了。

很显然：

在w[i]>=W时这个i矿石会在统计里（若<W就不管它了直接pre[i]=pre[i-1]），

矿石价值和是：pre_v[i]=pre_v[i-1]+v[i]，前面的和加上当前这一个i矿石;

矿石数量和是：pre_n[i]=pre_n[i-1]+1,数量加1嘛。

然后最后算的时候用右端点r-（左端点l-1）就可以了

注意：谨记所前缀和时要pre[r]-pre[l-1]，这个‘-1’不要忘！

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
using namespace std;

int n,m;
long long w[200010],v[200010],l[200010],r[200010];
long long q1[200010],q2[200010];
long long li,ri,s,ans;

long long check(int x)
{
    for(int i = 1;i <= n; ++i)
    {
        if(w[i] >= x)
        {
            q1[i] = q1[i - 1] + v[i];
            q2[i] = q2[i - 1] + 1;
        }
        else
        {
            q1[i] = q1[i - 1];
            q2[i] = q2[i - 1];
        }
    }
    long long Y = 0;
    for(int i = 0;i < m; ++i)
        Y += (q2[r[i]] - q2[l[i] - 1]) * (q1[r[i]] - q1[l[i] - 1]);
    return s - Y;
}

int main()
{
    scanf("%d%d%lld",&n,&m,&s);
    li = ri = 0;
    for(int i = 1;i <= n; ++i)
    {
        scanf("%lld%lld",&w[i],&v[i]);
        ri = max(ri,w[i]);
    }
    for(int i = 0;i < m; ++i)
        scanf("%lld%lld",&l[i],&r[i]);
    ans = 0x3f3f3f3f3f3f;
    while(li <= ri)
    {
        long long mid = (li + ri) / 2;
        long long u = check(mid);
        if(u == 0)
        {
            printf("0\n");
            return 0;
        }
        if(u < 0)
        {
            ans = min(-u,ans);
            li = mid + 1;
        }
        else
        {
            ri = mid - 1;
            ans = min(ans,u);
        }
    }
    printf("%lld\n",ans);
    return 0;
}

洛谷P1314 聪明的质监员 二分答案