2012-11-06 22:44:05Morris
[ZJ][掃描線] a570. 場地租借
內容 ：
| 場地租借 |
Background
小光寫演算法作業遇到一個場地租借的問題，場地只有一個，要安排場地給租借的人，每個租借都有其價值，但要在獲益最高， 由於每個租借都有一段時間，計算起來就相當複雜，接下來就靠會寫程式的你們。
The Problem
給定 N 個活動，接下來會給定 N 個活動的起始時間 S、結束時間 E、租借費用 V，求不衝突的最大獲益。
輸入說明
：
多筆測資，每筆第一行有一個 N 代表接下來有 N 行活動的敘述，每行上用 S，E，V 代表這個活動的起始時間、結束時間、租借費用。
1 ≦ N ≦ 3000, 1 ≦ S < E ≦ 1,000,000, 1 ≦ V ≦ 100,000
輸出說明
：
輸出最大獲益即可。
範例輸入 ：
4 1 3 5 2 5 6 4 7 3 6 9 4 2 1 2 3 2 3 6
範例輸出 ：
10 9
提示
：
※ 題目重覆，或者是測資問題請通知我。
出處
：
整體效率 O(nlogn)。感謝 inker 指導。
時間放寬是給 dp O(n^2) 過的, 怎麼做我想我不用多說。
#include <stdio.h>
#include <queue>
#include <vector>
using namespace std;
struct seg {
int s, e, v;
};
struct cmp1 {
bool operator() (seg a, seg b) {
return a.s > b.s;
}
};
struct cmp2 {
bool operator() (seg a, seg b) {
return a.e > b.e;
}
};
int main() {
int n, i, S, E, v;
while(scanf("%d", &n) == 1) {
priority_queue<seg, vector<seg>, cmp1> pQ1;
priority_queue<seg, vector<seg>, cmp2> pQ2;
seg e;
for(i = 0; i < n; i++) {
scanf("%d %d %d", &S, &E, &v);
e.s = S, e.e = E, e.v = v;
pQ1.push(e);
}
int pred = 0;
for(i = 0; i < n; i++) {
while(!pQ2.empty() && pQ2.top().e <= pQ1.top().s) {
pred = max(pred, pQ2.top().v);
pQ2.pop();
}
e = pQ1.top();
pQ1.pop();
e.v += pred;
pQ2.push(e);
}
while(!pQ2.empty() && pQ2.top().e) {
pred = max(pred, pQ2.top().v);
pQ2.pop();
}
printf("%d\n", pred);
}
return 0;
}