Portal
Portal1: Luogu
Portal2: LibreOJ
Portal3: Vijos
Description
小T是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有(n)个矿石，从(1)到(n)逐一编号，每个矿石都有自己的重量(w_i)以及价值(v_i)。检验矿产的流程是：
-
给定(m)个区间([L_i, R_i])；
-
选出一个参数(W)；
-
对于一个区间([L_i, R_i])，计算矿石在这个区间上的检验值(Y_i)：
这批矿产的检验结果(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 15
1 5
2 5
3 5
4 5
5 5
1 5
2 4
3 3
Sample Output
10
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<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
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 long
inline 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
", ans);
return 0;
}