前缀和优化水站

题目

思路

定义差分数组记录为从第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("%dn",ans);
    int tot=0;
    for(int i=pos;i<n;i++){
        tot+=w[i];
        if(tot<=l[i]){
            printf("%d ",i);
        }
    }
    printf("n");
}