Google CodeJam 2017 Round 1C Problem B

Posted on | In ,

Parenting Partnering

Abridge problem statement

有 A, B 兩人，每人一天都必須花 720 分鐘顧小孩，給定一些 A, B 各自不能顧小孩的時間，請你安排最少換手次數的顧小孩時間表。

Solution sketch

核心想法，如果 gap（就是 A 或是 B 有空的所有區間）兩端的事件都屬於 A 或是 B，那就看看能不能把區間的時間全部給 A 或是 B來顧，這樣可以少掉換手的次數。如果不行，那一定是 ABA 或是 BAB 了，所以一定會換手兩次。

如果 gap 兩端事件不同，那就一定換手一次。至於何時換手，不管。 (ABABA…AB 或是 BABABA…BA 都是沒有意義的分配，因為你一定可以 reduce 成 AB 或是 BA 就好)。

AC code

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<int, ii> gapi;
int main()
{
    int ncase;
    scanf("%d", &ncase);
    while (ncase--) {
        int a, b;
        scanf("%d %d", &a, &b);
        int atime = 0, btime = 0;
        vector<iii> inp;
        for (int i = 0; i < a; i++) {
            int s, t;
            scanf("%d %d", &s, &t);
            inp.push_back(iii(ii(s, t), 1));
            btime += (t - s);
        }
        for (int i = 0; i < b; i++) {
            int s, t;
            scanf("%d %d", &s, &t);
            inp.push_back(iii(ii(s, t), 2));
            atime += (t - s);
        }
        sort(inp.begin(), inp.end());
        vector<gapi> gap;
        int ans = 0;
        for (int i = 0; i < (int)inp.size(); i++) {
            int sz = (int)inp.size();
            int s1 = inp[(i - 1 + sz) % sz].first.first;
            int t1 = inp[(i - 1 + sz) % sz].first.second;
            int type1 = inp[(i - 1 + sz) % sz].second;
            int s2 = inp[i].first.first;
            int t2 = inp[i].first.second;
            int type2 = inp[i].second;
            if ((s2 == t1) || (s2 == 0 && t1 == 1440)) {
                if (type1 != type2)
                    ans++;
                continue;
            }
            gap.push_back(gapi((s2 - t1) > 0 ? (s2 - t1) : 1440 - abs(s2 - t1),
                               ii(type1, type2)));
        }
        sort(gap.begin(), gap.end());
        reverse(gap.begin(), gap.end());
        for (int i = (int)gap.size() - 1; i >= 0; i--) {
            bool ok = false;
            if (gap[i].second.first == gap[i].second.second) {
                int diff = gap[i].first;
                if (gap[i].second.first == 1) {
                    if (btime + diff <= 720) {
                        btime += diff;
                        ok = true;
                    }
                } else {
                    if (atime + diff <= 720) {
                        atime += diff;
                        ok = true;
                    }
                }
                if (ok == false)
                    ans += 2;
            } else {
                ans++;
            }
            gap.pop_back();
        }
        printf("Case #%d: %d\n", 100 - ncase, ans);
    }
    return 0;
}