二分+前缀和
#include <iostream> using namespace std; typedef long long ll; const int maxn = 200010; int w[maxn]; int v[maxn]; int l[maxn]; int r[maxn]; long long sum[maxn]; int cnt[maxn]; int n, m; ll ans = 0; ll s; long long judge(int num) { long long res = 0; for (int i = 1; i <= n; i++) { if (w[i] >= num) { sum[i] = sum[i - 1] + v[i]; cnt[i] = cnt[i - 1] + 1; } else { sum[i] = sum[i - 1]; cnt[i] = cnt[i - 1]; } } for (int i = 1; i <= m; i++) { res += (sum[r[i]] - sum[l[i]-1]) * (cnt[r[i]] - cnt[l[i]-1]); } return res; } int find(int l, int r) { while (l < r) { int mid = (r - l+1) / 2 + l; if (judge(mid)>=s)l = mid; else r = mid - 1; } return l; } int main() { cin >> n >> m >> s; for (int i = 1; i <= n; i++) { cin >> w[i] >> v[i]; } for (int i = 1; i <= m; i++) { cin >> l[i] >> r[i]; } int num= find(1, 1000000); cout << min(abs(judge(num) - s), abs(judge(num + 1) - s)); }