2012-11-27 08:39:39Morris
[ZJ][Greedy、並查集] a567. 死線排程
內容 ：
| 死線排程 |
Background
大學最常遇見的就是死線(deadline)，死線的選擇常常是大學生的煩惱，如何得到最大利益的排程？
The Problem
給 N 個作業，每個作業分別有 deadline 與 profit，在此分別以 di與pi 表示之，台灣的大學生很厲害每項作業都可以在一天的時間內完成，同時也很偷懶，最喜歡在最後一天才開始寫作業，意即在最後一天完成作業是可接受的。
現在是日期的第一天，請你安排他的工作。
輸入說明
：
多筆測資
每組第一行有一個數字 N 代表作業總數，
接下來有 N 行資料，每行上有兩個數字 di 與 pi 。
0 < N ≦ 10000, 0 < di ≦ 10000, 0 < pi <32767
輸出說明
：
排程方法數可能很多，輸出最大獲益即可。
範例輸入
：
6 2 5 3 6 4 4 4 2 5 3 5 1 8 7 1 7 1 7 1 10 1 11 1 9 1 10 1 11 1
範例輸出 ：
20 8
提示
：
小光偷看了一下 偷懶學生的排程。
範例測資一
| Day | 1 | 2 | 3 | 4 | 5 |
| Task | 4 | 1 | 2 | 3 | 5 |
範例測資二
| Day | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| Task | X | X | X | 8 | 3 | 2 | 1 | 7 | 6 | 4 | 5 |
測資不嚴謹、描述不清、題目類型重覆，感謝您的通知。
出處
：
I2A
(管理：morris1028)
依照價值由高到低排，接著去找可行解，放的位置採用 greedy，放在最鄰近 deadline 的一天，
如果不能放就捨棄，為了模擬上加快，這裡使用並查集去完成。
/**********************************************************************************/
/* Problem: a567 "死線排程" from I2A */
/* Language: CPP (1719 Bytes) */
/* Result: AC(60ms, 484KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2012-11-27 08:36:31 */
/**********************************************************************************/
#include <stdio.h>
#include <algorithm>
using namespace std;
struct task {
int d, p;
};
bool cmp(task a, task b) {
return a.p > b.p;
}
int p[10005], r[10005], inter[10005];
void init(int n) {
for(int i = 0; i <= n; i++)
p[i] = i, r[i] = 1, inter[i] = i;
}
int findp(int x) {
return p[x] == x ? x : (p[x]=findp(p[x]));
}
int joint(int x, int y) {
x = findp(x), y = findp(y);
if(x != y) {
if(r[x] > r[y]) {
p[y] = x, r[x] += r[y];
inter[x] = min(inter[x], inter[y]);
} else {
p[x] = y, r[y] += r[x];
inter[y] = min(inter[x], inter[y]);
}
return 1;
}
return 0;
}
int main() {
int n, i, x, y;
int sche[10005];
while(scanf("%d", &n) == 1) {
task A[10005];
int day = 1, ans = 0;
for(i = 0; i < n; i++) {
scanf("%d %d", &A[i].d, &A[i].p);
day = max(day, A[i].d);
}
day++;
for(i = 1; i <= day; i++)
sche[i] = 0;
sort(A, A+n, cmp);
init(day);
for(i = 0; i < n; i++) {
if(sche[A[i].d] == 0) {
x = y = A[i].d;
if(sche[x+1])
x++;
} else {
x = findp(A[i].d);
y = inter[x]-1;
if(!y) continue;
}
sche[y] = i+1;
ans += A[i].p;
joint(x, y);
if(y-1 > 0 && sche[y-1])
joint(y-1, y);
}
printf("%d\n", ans);
}
return 0;
}
/*
6
2 5
3 6
4 4
4 2
5 3
5 1
8
7 1
7 1
7 1
10 1
11 1
9 1
10 1
11 1
*/
依照價值由高到低排，接著去找可行解，放的位置採用 greedy，放在最鄰近 deadline 的一天，
如果不能放就捨棄，為了模擬上加快，這裡使用並查集去完成。
/**********************************************************************************/
/* Problem: a567 "死線排程" from I2A */
/* Language: CPP (1719 Bytes) */
/* Result: AC(60ms, 484KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2012-11-27 08:36:31 */
/**********************************************************************************/
#include <stdio.h>
#include <algorithm>
using namespace std;
struct task {
int d, p;
};
bool cmp(task a, task b) {
return a.p > b.p;
}
int p[10005], r[10005], inter[10005];
void init(int n) {
for(int i = 0; i <= n; i++)
p[i] = i, r[i] = 1, inter[i] = i;
}
int findp(int x) {
return p[x] == x ? x : (p[x]=findp(p[x]));
}
int joint(int x, int y) {
x = findp(x), y = findp(y);
if(x != y) {
if(r[x] > r[y]) {
p[y] = x, r[x] += r[y];
inter[x] = min(inter[x], inter[y]);
} else {
p[x] = y, r[y] += r[x];
inter[y] = min(inter[x], inter[y]);
}
return 1;
}
return 0;
}
int main() {
int n, i, x, y;
int sche[10005];
while(scanf("%d", &n) == 1) {
task A[10005];
int day = 1, ans = 0;
for(i = 0; i < n; i++) {
scanf("%d %d", &A[i].d, &A[i].p);
day = max(day, A[i].d);
}
day++;
for(i = 1; i <= day; i++)
sche[i] = 0;
sort(A, A+n, cmp);
init(day);
for(i = 0; i < n; i++) {
if(sche[A[i].d] == 0) {
x = y = A[i].d;
if(sche[x+1])
x++;
} else {
x = findp(A[i].d);
y = inter[x]-1;
if(!y) continue;
}
sche[y] = i+1;
ans += A[i].p;
joint(x, y);
if(y-1 > 0 && sche[y-1])
joint(y-1, y);
}
printf("%d\n", ans);
}
return 0;
}
/*
6
2 5
3 6
4 4
4 2
5 3
5 1
8
7 1
7 1
7 1
10 1
11 1
9 1
10 1
11 1
*/