题意：大致就是求最小费用的方案使得最后一层减压。分析：分析一下题意，假如我们从第i层开始减压，其下的所有层均需要减压(不管人工还是自动)，否则这种减压就是浪费的。因此我们可以枚举开始减压的层数。然而我们的目的是尽量使更多的层自动减压，并且已经自动减压的层不能再自动减压。由此得第i层自动减压的条件：假设此时开始减压为第j层，pre[]数组为水量的前缀和，那么有pre[j]-pre[i-1]>v[i](容量)，也就是从开始到这一层所有的水量大于容量时可以使其自动减压，变形一下即得：pre[j]>pre[i-1]+v[i]，因此对于pre[i-1]+v[i]我们可以建一个小根堆，每次判断出堆元素是否小于当前的pre[j]，，如果小于，出堆，更新当前的sumcost值，循环。之后再将pre[j-1]+v[i]入堆即可。在求值过程中统计答案即可。由于一层只会最多入堆出堆一次，插入时间为logn，因此总的时间复杂度为O(nlogn).#include <cstdio>#include <queue>#include <utility>using namespace std;const int MAXN = 15005, INF = 2e9;int n = 0;int v[MAXN] = {0}, s[MAXN] = {0}, c[MAXN] = {0};//容量v,已有s,代价cint pre[MAXN] = {0}; int main() {scanf("%d", &n);for(int i = n; i >= 1; –i) {scanf("%d%d%d", s+i, v+i, c+i);pre[i] = pre[i+1]+s[i];}int ans = INF, flag = 0, sum = 0;priority_queue<pair<int,int> > heap; for(int i = 1; i <= n; ++i){for(; !heap.empty() && heap.top().first > pre[i+1]; heap.pop())sum -= heap.top().second;heap.push(make_pair(pre[i]-v[i], c[i]));sum += c[i];if(ans > sum){ans = sum;flag = i;}}bool hash[MAXN] = {0};int sumf = 0;for(int i = flag; i >= 1; –i){sumf += s[i];if(sumf > v[i])hash[i] = true;}for(int i = flag; i >= 1; –i)if(!hash[i])printf("%d\n", n-i+1);return 0;}
既有美妙的风景，也会有称不上景只有风的地方。
