原题链接：https://www.luogu.org/problem/show?pid=1314
前缀和+二分答案的一道好题。
不难看出这个W和矿石的重量是有关系的。矿石的重量的最大值和最小值可以记录出来，这样W便有界。根据题意W所在区间显然可以单调，所以可以使用二分进行求解。
我们二分W，然后去计算以这个W为答案的值与标准值相比较。
二分的check函数用前缀和维护就可以。通常的做法是开两个数组，一个sumval记录每个矿石价值的前缀和，一个sumnum记录选取矿石数量的前缀和。
为什么选这两个前缀和？看公式啊，Y值就是要用这两个数算出来的。
我们枚举每一个矿石，如果发现有一个w[i] > w ，那么sumval[i] = sumva[i-1] + v[i] , sumnum[i] = sumnum[i-1] + 1，否则sumval[i] = sumval[i-1] ， sumnum[i] = sumnum[i-1]。
二分的时候顺带维护一个ans，最后的答案就是了。
参考代码：
1 #include2 #include 3 #include 4 #include 5 #define maxn 200005 6 typedef long long ll; 7 const ll LINF = 1926081719260817; 8 long long int read(){ 9 long long int num = 0; 10 char c; 11 bool flag = false; 12 while ((c = getchar()) == ' ' || c == ' ' || c == ' '); 13 if (c == '-') 14 flag = true; 15 else 16 num = c - '0'; 17 while (isdigit(c = getchar())) 18 num = num * 10 + c - '0'; 19 return (flag ? -1 : 1) * num; 20 } 21 ll n,m,s,ans = LINF; 22 ll w[maxn],v[maxn]; 23 ll interval_left[maxn],interval_right[maxn]; 24 ll sumval[maxn],sumnum[maxn]; 25 26 ll lmax(ll x,ll y){ 27 return x>y? x : y; 28 } 29 ll labs(ll x){ 30 return x>0? x : -x; 31 } 32 bool check(ll mid){ 33 ll val_Y = 0; 34 memset(sumnum,0,sizeof(sumnum)); 35 memset(sumval,0,sizeof(sumval)); 36 for (register ll i=1;i<=n;i++){ 37 if (w[i] > mid){ 38 sumval[i] = sumval[i-1] + v[i]; 39 sumnum[i] = sumnum[i-1] + 1; 40 } 41 else{ 42 sumval[i] = sumval[i-1]; 43 sumnum[i] = sumnum[i-1]; 44 } 45 } 46 for (register ll i=1;i<=m;i++) 47 val_Y += (sumval[interval_right[i]] - sumval[interval_left[i]-1]) * (sumnum[interval_right[i]] - sumnum[interval_left[i]-1]); 48 ans = std::min(ans,labs(val_Y - s)); 49 if (val_Y > s) 50 return true; 51 else 52 return false; 53 54 } 55 56 int main(){ 57 n = read();m = read();s = read(); 58 ll l = 0;ll r = -1;ll mid; 59 for (register ll i=1;i<=n;i++){ 60 w[i] = read();v[i] = read(); 61 r = lmax(r,w[i]); 62 } 63 r++; 64 for (register ll i=1;i<=m;i++){ 65 interval_left[i] = read();interval_right[i] = read(); 66 } 67 while (l < r){ 68 mid = (l + r) >> 1; 69 if (check(mid)) 70 l = mid + 1; 71 else 72 r = mid; 73 } 74 printf("%lld ",ans); 75 return 0; 76 }