『题解』洛谷P1314 聪明的质监员-白红宇

『题解』洛谷P1314 聪明的质监员

阅读量：4708 次

发布时间：2019-06-10

本文共 2644 字，大约阅读时间需要 8 分钟。

Portal

Portal1:

Portal2:

Portal3:

Description

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

给定$m$个区间$[L_i, R_i]$；

选出一个参数$W$；

对于一个区间$[L_i, R_i]$，计算矿石在这个区间上的检验值$Y_i$：

$Y_i=\sum_j1 \times \sum_j{v_j},\ j\in[L_i, R_i]$ 且 $w_j\ge W,\ j$是矿石编号

这批矿产的检验结果$Y$为各个区间的检验值之和。即：$Y_1 + Y_2 + \cdots +Y_m$。

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

Input

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

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

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

Output

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

Sample Input

5 3 151 52 53 54 55 51 52 43 3

Sample Output

Sample Explain

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

Hint

对于$10\%$的数据，有$1 \le n, m \le 10$；

对于$30\%$的数据，有$1 \le n, m \le 500$；

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

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

对于$100\%$的数据，有$1 \le n, m \le 200,000 ,0 < w_i, v_i \le 10^6,0 < S \le 10^{12},1 \le L_i \le R_i \le n$。

Solution

这道题直接在$[0, \max{w[i]}]$二分枚举$W$，对于每一个枚举出来的$w$，暴力计算每一个区间的检验值和，这里使用前缀和优化。

Code

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;typedef long long LL;const LL INF = 0x7f7f7f7f7f7f7f7f7f7f;//把ans的初始值设大一点，否则会WA很多const int MAXN = 200005;int n, m, w[MAXN], v[MAXN], L[MAXN], R[MAXN];LL S, l, r, mid, ans, sum1[MAXN], sum2[MAXN];//注意开long longinline bool check(LL x) {    for (int i = 1; i <= n; i++)        if (x <= w[i]) {//如果符合要求的化            sum1[i] = sum1[i - 1] + 1;            sum2[i] = sum2[i - 1] + v[i];        } else {            sum1[i] = sum1[i - 1];            sum2[i] = sum2[i - 1];        }    LL s = 0;    for (int i = 1; i <= m; i++)        s += (sum2[R[i]] - sum2[L[i] - 1]) * (sum1[R[i]] - sum1[L[i] - 1]);//暴力计算每一个区间，累加起来    if (ans > fabs(s - S)) ans = fabs(s - S);//计算与标准值相差的最小值    if (S > s) return 1; else return 0;}int main() {    scanf("%d%d%lld", &n, &m, &S);    for (int i = 1; i <= n; i++) {        scanf("%d%d", &w[i], &v[i]);        if (w[i] > r) r = w[i];//求区间的右边界（取w[i]的最大值）    }    for (int i = 1; i <= m; i++)        scanf("%d%d", &L[i], &R[i]);    r++;    l = 0;    ans = INF;    while (l < r) {        mid = l + r >> 1;//二分枚举        if (check(mid)) r = mid; else l = mid + 1;//如果大于标准值就往降低要求，否则就提高要求    }    printf("%lld\n", ans);    return 0;}

Attachment

测试数据下载：

转载于:https://www.cnblogs.com/shenxiaohuang/p/11221159.html

你可能感兴趣的文章