题目描述
首先此题有个巨坑,就是每个区间可以重复选(我也是看别的网站的样例解释才看明白的,建议y总加一个样例解释)。
其次,由于S过大,所以S应该设置为longlong类型。
样例
5 3 15
1 5
2 5
3 5
4 5
5 5
1 5
2 4
3 3
10
样例说明:当W选4的时候,三个区间上检验值分别为20、5、0,这批矿产的检验结果为25,此时与标准值S相差最小为10。
(其他网站的样例说明)
算法1
(二分+前缀和) $O(nlogn)$
思路;二分W的值,当确定W的值之后构造v[i]的前缀和,然后用其前缀和与S作比较,当比S小时则W应该取小一点。
注意;不能先构造v[i]的前缀和,因为不知道v[i]与W之间的关系,所以即使构造了也用不上。
C++ 代码
//1.二分W
//2.构造前缀和
//每个区间可以重复选
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1e6+10;
typedef long long ll;
typedef pair<int,int> pii;
int n,m,maxv;
int w[N],v[N],s1[N];
ll s[N],c;
pii a[N];
ll res=1e12+10;//注意这里可能出现S特别大,Y特别小,所以res需设置为longlong型
bool check(int mid)//mid即W,这里二分有个技巧就是前缀和可以写在二分里面,我觉得这个很有用。
{
ll sum=0;
int num=0;
memset(s,0,sizeof s);
memset(s1,0,sizeof s1);
for(int i=1;i<=n;i++)
if(w[i]>=mid) {
s[i]=s[i-1]+(ll)v[i];
s1[i]=s1[i-1]+1;//构造num前缀和,即此区间有多少个数大于W
}
else s[i]=s[i-1],s1[i]=s1[i-1];
for(int i=1;i<=m;i++) sum+=(s[a[i].second]-s[a[i].first-1])*(ll)(s1[a[i].second]-s1[a[i].first-1]);
ll temp=abs(c-sum);
res=min(res,temp);
return sum<=c;
}
int main()
{
cin>>n>>m>>c;
for(int i=1;i<=n;i++) scanf("%d%d",&w[i],&v[i]),maxv=max(maxv,w[i]);//cin>>w[i]>>v[i],maxv=max(maxv,w[i]);
for(int i=1;i<=m;i++) scanf("%d%d",&a[i].first,&a[i].second);//cin>>a[i].first>>a[i].second;
int l=1,r=maxv+1;//二分W,注意这里有个maxv+1,当S特别小而Wi特别大时此时什么都不选才能使S-Y最小!!!
while(l<r)
{
int mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
printf("%lld",res);
return 0;
}