思路
二分答案加前缀和，二分答案自然不难想，就是这个前缀和。。。
用sum_v和sum_w分别记录两组前缀和。记录方式如下
for(register int i=1; i<=n; i++) {
if(w[i] < mid) {
sum_v[i] = sum_v[i-1];
sum_w[i] = sum_w[i-1];
}
else {
sum_v[i] = sum_v[i-1] + v[i];
sum_w[i] = sum_w[i-1] + 1;
}
}
吐槽
我调了很久，知道为什么吗
因为输入l和r的时候输入的l和v，把v的值都改变了，硬是调颓废了半下午
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long LL;
const int maxn = 2e5+3;
const LL INF = 999999999999999;
using namespace std;
LL n, m, s, sum_v[maxn], sum_w[maxn], Ans, ans = INF, sum;
LL w[maxn], v[maxn], mx = -1, mn = INF, l[maxn], r[maxn];
inline bool judge(int mid) {
Ans = 0;
memset(sum_v, 0, sizeof(sum_v));
memset(sum_w, 0, sizeof(sum_w));
for(register int i=1; i<=n; i++) {
if(w[i] < mid) {
sum_v[i] = sum_v[i-1];
sum_w[i] = sum_w[i-1];
}
else {
sum_v[i] = sum_v[i-1] + v[i];
sum_w[i] = sum_w[i-1] + 1;
}
}
for(register int i=1; i<=m; i++)
Ans += (sum_v[r[i]]-sum_v[l[i]-1]) * (sum_w[r[i]]-sum_w[l[i]-1]);
sum = llabs(s-Ans);
if(Ans > s) return true;
else return false;
}
int main() {
scanf("%lld%lld%lld", &n, &m, &s);
for(register int i=1; i<=n; i++) {
scanf("%lld%lld", &w[i], &v[i]);
mx = max(mx, w[i]);
mn = min(w[i], mn);
}
for(register int i=1; i<=m; i++) {
scanf("%lld%lld", &l[i], &r[i]);
}
int ll = mn-1, rr = mx+2, mid;
while (ll <= rr) {
mid = (ll + rr)>>1;
if(judge(mid))
ll = mid+1;
else rr = mid-1;
ans = min(ans, sum);
}
printf("%lld", ans);
}
转载于:https://www.cnblogs.com/bljfy/p/9343291.html
相关资源：锣鼓声声迎新春——新年工作计划ppt模板.zip
