499聪明的质监员
瞅一眼这个题。。。
嗯,二分
so 代码如下
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 200000 + 10;
const int maxw = 1000000 + 10;
typedef long long LL;
int n, m;
LL S;
int l[maxn], r[maxn];
int v[maxn], w[maxn];
LL pre_cnt[maxn], pre_sum[maxn];
LL clt (int W)
{
LL ret = 0;
pre_cnt[0] = pre_sum[0] = 0;
for (int i = 1; i <= n; i++)
{
pre_cnt[i] = pre_cnt[i-1];
pre_sum[i] = pre_sum[i-1];
if (w[i] >= W)
{
pre_cnt[i]++;
pre_sum[i] += v[i];
}
}
for (int i = 0; i < m; i++)
ret += (pre_cnt[r[i]]-pre_cnt[l[i]-1]) * (pre_sum[r[i]]-pre_sum[l[i]-1]);
return ret;
}
int main ()
{
cin >> n >> m >> S;
for (int i = 1; i <= n; i++)
scanf("%d%d", &w[i], &v[i]);
for (int i = 0; i < m; i++)
scanf("%d%d", &l[i], &r[i]);
int L = *min_element(w+1, w+n+1);
int R = *max_element(w+1, w+n+1);
while (R - L > 1)
{
int M = L + (R-L)/2;
if (clt(M) > S) L = M; else R = M;
}
LL ans = min(abs(clt(L)-S), abs(clt(R)-S));
cout << ans;
return 0;
}