这道题最关键的就是看懂题目中的
数学式
这个说人话就是
在访问的区间内 符合中括号里的矿石的个数和重量的积
就是Y
观察每个区间的值
Yi=(∑j1)∗(∑jvj)
j∈[Li,Ri]且wj≥WYi=(∑j1)∗(∑jvj),j∈[Li,Ri]且wj≥W
当 W 增大时，区间 [Li,Ri][Li,Ri] 中满足要求的 (wi,vi)(wi,vi) 会减少，同时所有 vi≥0vi≥0，因此 Yi 的值也会减少。
由于 Y=∑iYiY=∑iYi，所以 Y 随 W 单调递减
因此我们可以二分出距离 S 最近的值
加上前缀和优化即可
附上菜鸡代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=200010;
int n,m;
LL s;
int w[N],v[N];
int R[N],L[N];
LL sum[N];
int cnt[N];
LL get(int W)
{
for(int i=1;i<=n;i++)
{
if(w[i]>=W)
{
sum[i]=sum[i-1]+v[i];
cnt[i]=cnt[i-1]+1;
}
else
{
sum[i]=sum[i-1];
cnt[i]=cnt[i-1];
}
}
LL ans=0;
for(int i=0;i<m;i++)
{
ans+=(cnt[R[i]]-cnt[L[i]-1])*(sum[R[i]]-sum[L[i]-1]);
}
return ans;
}
int main()
{
scanf("%d%d%lld",&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=0,r=1e6+1;
while(l<r)//二分
{
int mid=l+r+1>>1;
if(get(mid)>=s)
{
l=mid;
}
else
{
r=mid-1;
}
}
printf("%lld\n",min(abs(get(r)-s),abs(s-get(r+1))));
return 0;
}
共 1 条回复