代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int n, m, w[N], v[N], l[N], r[N];
LL s, sw[N], sv[N], ans;//前缀和
int x, y;//二分范围
int main(){
cin >> n >> m >> s;
ans = s;//差值初始化
for(int i = 1; i <= n; i ++){
cin >> w[i] >> v[i];
y = max(y, w[i]);
}
x = 0, y = y + 1;
for(int i = 1; i <= m;i ++){
cin >> l[i] >> r[i];
}
while(x < y){
memset(sw, 0, sizeof(sw));
memset(sv, 0, sizeof(sv));
int W = (x + y) >> 1;
for(int i = 1; i <= n; i ++){
if(w[i] >= W){
sw[i] = sw[i - 1] + 1;
sv[i] = sv[i - 1] + v[i];
}else{
sw[i] = sw[i - 1];
sv[i] = sv[i - 1];
}
}
LL sum = 0;
for(int i = 1; i <= m; i ++){
sum += (LL)(sw[r[i]] - sw[l[i] - 1]) * (sv[r[i]] - sv[l[i] - 1]);
}
if(sum == s){
ans = 0;
break;
}else{
ans = min(ans, abs(s - sum));
if(sum > s){
//W小了
x = W + 1;
}else{
y = W;
}
}
}
cout << ans;
return 0;
}
while(x<y), x = mid + 1, y = mid
与 while(x<=y), x = mid + 1, y = mid - 1
有什么区别?