2012年12月5日 星期三

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

沒有留言:

張貼留言