這一回超難啊！觀察題超棒，演算法題更是把臉打得腫腫的啊QQ

B - Five Dishes

實作上要想一下，怎麼處理每十分鐘才能點餐的問題。

至於求最佳解，可以直接窮舉。

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


#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

int main()
{
    int inp[5];
    for (int i = 0; i < 5; i++)
        scanf("%d", &inp[i]);
    sort(inp, inp + 5);

    int mn = INT_MAX, sum = 0;
    do {
        sum = 0;
        for (int i = 0; i < 5; i++) {
            sum += inp[i];
            if (i < 4 && sum % 10 > 0)
                sum += 10 - sum % 10;
        }
        mn = min(mn, sum);
    } while (next_permutation(inp, inp + 5));

    printf("%d\n", mn);

    return 0;
}

C - Five Transportations

這題真的太神了。

主要的觀察就是，如果你把 bottleneck 找出來，我們從源頭送人時，就只送那個 bottleneck 的人數，就變超好算的啦！

舉例來說，sample test 1 是 $3\ 2\ 4\ 3\ 5$，bottleneck 為 2，那你就一個時間單位時間就送兩人就好，因為這樣每一個單位時間每一組人都一定可以不用等就通過每一個城市（不會塞），而且也保證這樣不會比其他送法的最佳解差。

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


#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

int main()
{
    ll n;
    scanf("%lld", &n);
    ll mn = LLONG_MAX;
    for (int i = 0; i < 5; i++) {
        ll num;
        scanf("%lld", &num);

        mn = min(mn, num);
    }

    ll group = (n + mn - 1) / mn;
    printf("%lld\n", 5 + group - 1);

    return 0;
}

D - Cake 123

兩種做法。

AC Code 1

我們做 BFS!

我們知道最大的一定是 X Y Z 最大的數字的組合，那下一個可能組合呢？X 換次大 or Y 換次大 or Z 換次大，對吧？這就是 BFS 的精神呀！

所以說，做法就是把每一種組合看成一個 node ，把 next steps 推進 priority queue 就好了！

 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


#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, pair<int, int>> iii;

const int N = 3333;
ll inpX[N], inpY[N], inpZ[N];
struct Node {
    int x, y, z;
    bool operator<(const Node &others) const
    {
        ll s1 = inpX[x] + inpY[y] + inpZ[z];
        ll s2 = inpX[others.x] + inpY[others.y] + inpZ[others.z];

        return s1 < s2;
    }

    ll val()
    {
        return inpX[x] + inpY[y] + inpZ[z];
    }
};

int main()
{
    int x, y, z, k;
    scanf("%d %d %d %d", &x, &y, &z, &k);

    for (int i = 0; i < x; i++)
        scanf("%lld", &inpX[i]);
    sort(inpX, inpX + x);
    for (int i = 0; i < y; i++)
        scanf("%lld", &inpY[i]);
    sort(inpY, inpY + y);
    for (int i = 0; i < z; i++)
        scanf("%lld", &inpZ[i]);
    sort(inpZ, inpZ + z);

    priority_queue<Node> pq;
    set<iii> used;
    used.insert({x - 1, {y - 1, z - 1}});
    pq.push({x - 1, y - 1, z - 1});
    while (pq.size() > 0 && k--) {
        Node cur = pq.top();
        pq.pop();
        printf("%lld\n", cur.val());

        if (cur.x > 0) {
            auto newNode = cur;
            newNode.x--;
            iii c = {newNode.x, {newNode.y, newNode.z}};
            if (used.find(c) == used.end())
                pq.push(newNode), used.insert(c);
        }
        if (cur.y > 0) {
            auto newNode = cur;
            newNode.y--;
            iii c = {newNode.x, {newNode.y, newNode.z}};
            if (used.find(c) == used.end())
                pq.push(newNode), used.insert(c);
        }
        if (cur.z > 0) {
            auto newNode = cur;
            newNode.z--;
            iii c = {newNode.x, {newNode.y, newNode.z}};
            if (used.find(c) == used.end())
                pq.push(newNode), used.insert(c);
        }
    }

    return 0;
}

AC code 2

先把 $X$ 跟 $Y$ 的所有組合枚舉出來 (放進 $P$)，之後把 $P$ 跟 $Z$ 的前 $K$ 大的數字再拿出來枚舉所有組合，之後取前 $K$ 個數字即可。

這樣可以過的原因是過程中枚舉一個是 $O(X * Y)$ 一個是 $O(K * K)$ ，即使加上排序，也才多個 $log$ 而已。

 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


#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

int main()
{
    int x, y, z, k;
    scanf("%d %d %d %d", &x, &y, &z, &k);

    ll inpX[x], inpY[y], inpZ[z];
    for (int i = 0; i < x; i++)
        scanf("%lld", &inpX[i]);
    for (int i = 0; i < y; i++)
        scanf("%lld", &inpY[i]);
    for (int i = 0; i < z; i++)
        scanf("%lld", &inpZ[i]);
    sort(inpZ, inpZ + z);
	
    ll cand[x * y];
    for (int i = 0; i < x; i++)
        for (int j = 0; j < y; j++)
            cand[i * x + j] = inpX[i] + inpY[j];
    sort(cand, cand + x * y); 

    vector<ll> ans;
    for (int xx = max(0, x * y - k); xx < x * y; xx++)
        for (int yy = max(0, z - k); yy < z; yy++) {
            ans.push_back(cand[xx] + inpZ[yy]);
        }
    sort(ans.begin(), ans.end());
    reverse(ans.begin(), ans.end());

    for (int xx = 0; xx < k; xx++) {
        printf("%lld\n", ans[xx]);
    }

    return 0;
}