Problem Solving►ZeroJudge

ZeroJudge a567 - 死線排程

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址

Solution

每次都先考慮獲利最高的，所以先將各作業依 profit 排序。
接著有兩種做法，先講 $O(n^2)$ 的:

每次取出還未排進可行集合內的，接著從它的 deadline 開始向左找，只要可以填進去就填，不行就捨去。

而這個過程我們可以透過 Disjoint-set 來加速至 $O(nlogn)$ ，用 day[i] 來記錄死線為 i 時，可填的時間區間。每次填入後，代表此可行區間又少一個可填的，所以將它和上一個天數的區間合併。

Union(item[i].dead, day[item[i].dead] - 1)

舉例來說有 4 個工作以排序: [3,1,2,2]

day[]  1  2  3
       1  2  3

填入 3 ，第 3 天的可行區間減少一天，所以變為第 2 天的區間 

day[]  1  2  3
       1  2  2

填入 1 ，第 1 天的可行區間減少一天，變為 0 ，無法再放入作業

day[]  1  2  3
       0  2  2

填入 2 ， 第 2 天的可行區間減少一天，所以變為第 1 天的區間

day[]  1  2  3   
       0  1  2

(disjoint set 過程)

day[]  1  2  3
       0  0  0

無法填入 2 ，第 2 天的可行區間已為 0 ，代表它前面沒地方可填了。

結束

Code

ZJ a567ZJ a567
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//O(n^2)
#include<cstdio>
#include<algorithm>
#define N 10001
using namespace std;

struct Item
{
    int dead, p;
}item[N];

int main()
{
    int n, i;
    bool day[N];
    while (scanf("%d", &n) != EOF)
    {
        int max = 0;
        for (i = 0; i < n; i++)
        {
            scanf("%d%d", &item[i].dead, &item[i].p);
            if (max < item[i].dead)
                max = item[i].dead;
        }
        sort(item, item + n, [](const Item& a, const Item& b)->bool
        {
            return a.p > b.p;
        });

        int sum = 0,j;
        //init
        for (i = 0; i <= n; i++)
            day[i] = false;
        for (i = 0; i < n; i++)
        {
            for (j = item[i].dead; j; j--)
                if (!day[j])
                    break;
            
            if (j)
            {
                sum += item[i].p;
                day[j] = true;
            }
        }

        printf("%d\n", sum);
    }

    return 0;
}

disjoint set

ZJ a567ZJ a567
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<cstdio>
#include<algorithm>
#define N 10001

using namespace std;
struct Item
{
    int dead, p;

}item[N];

int day[N];
inline int find(int a);
inline void Union(int a, int b);
int main()
{
    int n, i;
    while (scanf("%d", &n) != EOF)
    {
        int max = 0;
        for (i = 0; i < n; i++)
        {
            scanf("%d%d", &item[i].dead, &item[i].p);
            if (max < item[i].dead)
                max = item[i].dead;
        }
        sort(item, item + n, [](const Item& a, const Item& b)->bool
        {
            return a.p > b.p;
        });

        int sum = 0, j;
        //init disjoint set
        for (i = 0; i <= max; i++)
            day[i] = i;

        //每個 day[] 表目前可放的區間
        for (i = 0; i < n; i++)
        {
            if (find(item[i].dead))
            {
                sum += item[i].p;
                //將目前item放入，從此deadline向左，可以放的位置
                Union(item[i].dead, day[item[i].dead] - 1);//注意參數順序有影響
            }
        }

        printf("%d\n", sum);
    }

    return 0;
}
int find(int a)
{
    return day[a] == a ? a : (day[a] = find(day[a]));
}
void Union(int a, int b)
{
    day[find(a)] = find(b);
}