题目大意
- 已知有一个n层的水站:
- Wi表示未操作之前第i层的已有水量；
- Li表示第i个水站能够维持或者储存的水的重量；
- Pi表示在第i层进行减压放水操作所需的费用.
- 被压减放水层所储存的所有水都将流向下一层。如果第i层的水量比Li大,则这一层也会（自动）减压(不需要任何费用)。
- 现在想要使最后一层减压(第n级)，求最少的花费。这个任务现在交给了你。
输入格式
- 每个输入的第一行包含一个自然数n(1 =< n <= 150000）
- 接下来n行每行包含3个数Wi，Li，Pi。
输出格式
- 第一行输出所需的最小费用
- 第二行若干个整数，从小到大输出必须减压的层的编号。
样例
样例输入
3
1000 1000 1
0 1000 2
2 10 100
样例输出
3
1 2
算法分析
- 模拟很好想吧 首先先来看一个事实： 如果当前节点i是第一个花钱把它减压的 那么从i到n一定所有的节点都减压了 因为如果在中间的某个节点没有减压的话 那么它前面的减压花费相当于白给
- 但是模拟会T 所以我们要准备想正解了
- 如果假设当前节点为k 在节点k之前有一个节点i 如果从i之前开始那么k不需要主动减压 从i之后开始需要主动减压（i越靠前到k处的水就越多 很容易 自己想）
- 而关于这个节点的位置我们可以二分查找
- 然后我们定义 ci 为从第 i 层开始放水一直放到第 n 层所需的费用. 考虑第 k 层的强制放水花费会对整个 ⟨ci⟩ 产生什么样的影响. 显然有当且仅当从第 i 层到第 k 层的总水量都不足以使第 k 层自动减压时 ci 中会包含第 k 层的强制放水费用. 因为当 k 不变时总水量随着 i 的减少而单调增加, 所以合法的 i 必然是比 k 小的连续一段, 二分找到最小的 i , 把最小的 i 到 k 之间的所有 ci 都加上 k 的花费即可. 而这个操作可以通过简单的前缀和解决. 总时间复杂度是 O(nlogn).
代码展示
#include<bits/stdc++.h>
using namespace std;
const int maxn = 15e4+10;
int n;
int w[maxn],l[maxn],p[maxn];
int sum[maxn],v[maxn];
int now,ans = 0x3f3f3f3f;
int main(){
scanf("%d",&n);
for(int i = 1;i <= n;++i){
scanf("%d%d%d",&w[i],&l[i],&p[i]);
sum[i] = sum[i-1] + w[i];
}
for(int i = 1;i <= n;++i){
int L = 1,R = i;
while(L < R) {
int mid = (L + R) >> 1;
if(sum[i] - sum[mid - 1] <= l[i])R = mid;
if(sum[i] - sum[mid - 1] > l[i])L = mid + 1;
}
v[R] += p[i];
v[i+1] -= p[i];
}
for(int i = 1;i <= n;++i){
v[i] += v[i-1];
if(ans > v[i])ans = v[i],now = i;
}
printf("%d
",ans);
for(int i = now;i <= n;++i)
if(sum[i] - sum[now - 1] <= l[i])printf("%d ",i);
return 0;
}