2018-06-19 18:26:49

### 【问题描述】

1、给定 m 个区间[Li，Ri]；

2、选出一个参数 W；

3、对于一个区间[Li，Ri]，计算矿石在这个区间上的检验值 Yi ：

5 3 15

1 5

2 5

3 5

4 5

5 5

1 5

2 4

3 3

10

### 【数据范围】

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define N 200001
#define M 200001
#define ll long long
using namespace std;
int n,m,l[M],r[M],v[N],w[N];
int maxw;
ll ans,tmp,s;
ll sumv[N],sumi[N];
ll judge(int W){
ll res = 0;
sumv[0] = sumi[0] = 0ll;
for(int i = 1;i <= n;i++){
if(w[i] >= W)sumv[i] = sumv[i - 1] + (ll)v[i],sumi[i] = sumi[i - 1] + 1ll;
else sumv[i] = sumv[i - 1],sumi[i] = sumi[i - 1];
}
for(int i = 1;i <= m;i++)
res += (sumi[r[i]] - sumi[l[i] - 1]) * (sumv[r[i]] - sumv[l[i] - 1]);
return res;
}
int main()
{
scanf("%d %d %lld",&n,&m,&s);
for(int i = 1;i <= n;i++)
scanf("%d %d",&w[i],&v[i]),maxw = max(maxw,w[i]);
for(int i = 1;i <= m;i++)
scanf("%d %d",&l[i],&r[i]);
int L = 1,R = maxw;
while(L <= R){
int mid = (L + R) / 2;
tmp = judge(mid);
if(tmp <= s)R = mid - 1;
else L = mid + 1;
if(abs(s - ans) > abs(tmp - s))ans = tmp;
}
printf("%lld",abs(ans - s));
return 0;
}
• star
首页