前缀和优化水站

题目

思路

定义差分数组记录为从第i层一直放水到第n层的花费，考虑第k层在某一层i开始放水时，到第k层必须强制放水，因为水从上向下传递的时候，肯定是越来越多的，所以一定存在一层i，从第i层开始放水，到第k层必须强制放水，然后c[i]+v[k],c[k+1]-v[k]，进行区间修改，因为数据有点大，在查询i时可以进行二分查找。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=150000+10;
int w[maxn],sum[maxn],l[maxn],v[maxn],c[maxn];
int main(){
	int n;scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&w[i],&l[i],&v[i]);
		sum[i]=sum[i-1]+w[i];
	}	
	for(int i=1;i<=n;i++){
		int x=lower_bound(sum,sum+1+n,sum[i]-l[i])-sum;
		x++;
		c[x]+=v[i];
		c[i+1]-=v[i];
	}
	int ans=0x3f3f3f3f;
	int pos=0;
	for(int i=1;i<=n;i++){
		c[i]=c[i]+c[i-1];
		if(c[i]<ans){
			ans=c[i];
			pos=i;
		}
	}
	printf("%d
",ans);
	int tot=0;
	for(int i=pos;i<n;i++){
		tot+=w[i];
		if(tot<=l[i]){
			printf("%d ",i);
		}
	}
	printf("
");
}