SGU 148 B-Station

題目敘述：

有N層，每一層有該層目前水的體積及該層的容量，可以手動放水（但要付錢），水會放到下一層。如果水滿了則會自動放水，現在我們要使最後一層放水，問最少需要花費多少錢

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

一開始有兩種思緒：

1. 背包，因為只會需要水最多到N，且有N層，因此複雜度O(N^2)
2. 枚舉，從哪裡開始放，然後要讓他一路通暢（不然前面就白花錢了），複雜度O(N^2)

        其實常寫程式的人，很容易就想到第一種，但是因為這題N到100000，所以很明顯是行不通的，而且也很難去優化他，會讓你有種走錯路的感覺。

       至於第二種思路，倒是比較難想到（可能是因為太基礎了，或是太簡單了）不過若是想到了，便接近正解了。接下來你會發現從最後一層開始枚舉的話，其實前面的那些人越有可能可以自動放水，因為你可以用一個 heap 去維護，每一個人進入heap一次，出去一次。整體複雜度O(nlgn)

這麼說起來，把東西看簡單一點，還是比較好些～～～

//By momo
#include<queue>
#include<cstdio>
#include<algorithm>

#define N 15010
#define F first
#define S second
#define INF 999999999

using namespace std;

typedef pair<int,int> PII;
priority_queue<PII> que, ans;
int n, w[N], l[N], p[N], sum[N];

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];
    }

    int bst = INF, mon = 0;
    for(int i = n; i >= 1; i--){
        mon += p[i];
        for(; !que.empty() && que.top().F > sum[i-1]; que.pop())
            mon -= p[que.top().S];
        que.push(make_pair(sum[i]-l[i], i));
        if(mon < bst) bst = mon, ans = que;
    }
    for(; !ans.empty(); ans.pop())
        printf("%d\n", ans.top().S);
}