洛谷 P1314 聪明的质监员（二分查找，前缀和）

二分查找，前缀和
本题要点：
1、首先， s 很大，所有用 long long 来存数组 w, v 和前缀和。
2、sum_num[i] 表示前 i 个位置， w值大于等于W 的数量;
sum_v 表示前 i 个位置， w值大于等于W 的 v 值的累加和;
3、 二分 W, 计算每个区间的 y[i] 值， 累加得到 y 值。
二分得到第一个使得 y 值小于等于 s 的 W 值（此时取值 L）， 那么 W - 1 所计算得到的y值，可能是第一个大于等于 s 的。
因此比较 W 取值 L 和 L - 1 ，看哪个更接近 s。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int MaxN = 2e5 + 10;
long long w[MaxN], v[MaxN];
long long sum_num[MaxN], sum_v[MaxN];
int n, m;
long long s, max_w;
int L[MaxN], R[MaxN];void calc_pre(long long mid)	// 计算前缀和
{
    sum_num[0] = sum_v[0] = 0;for(int i = 1; i <= n; ++i){
    if(w[i] >= mid){
    sum_num[i] = sum_num[i - 1] + 1;sum_v[i] = sum_v[i - 1] + v[i];}else{
    sum_num[i] = sum_num[i - 1];sum_v[i] = sum_v[i - 1];}}
}long long calc_y(long long mid)
{
    calc_pre(mid);long long y = 0;for(int i = 1; i <= m; ++i){
    y += (sum_num[R[i]] - sum_num[L[i] - 1]) *(sum_v[R[i]] - sum_v[L[i] - 1]);}return y;
}void solve()
{
    long long l = 0, r = max_w + 1, mid;while(l < r){
    mid = (l + r) / 2;if(calc_y(mid) <= s)	//计算第一个小于等于 s 的 W{
    r = mid;			}else{
    l = mid + 1;}}
// printf("res = %d, l = %d\n", calc_y(l), l);long long ans1 = abs(calc_y(l) - s), ans2 = abs(calc_y(l - 1) - s); long long ans = ans1 < ans2 ? ans1 : ans2;printf("%lld\n", ans);
}int main()
{
    scanf("%d%d%lld", &n, &m, &s);for(int i = 1; i <= n; ++i){
    scanf("%lld%lld", &w[i], &v[i]);if(w[i] > max_w)max_w = w[i];}for(int i = 1; i <= m; ++i){
    scanf("%d%d", &L[i], &R[i]);}solve();return 0;
}/* 5 3 15 1 5 2 5 3 5 4 5 5 5 1 5 2 4 3 3 *//* 10 */