題目： UVa - 11633 - Food portion sizes

題目說明

學生餐廳為了不讓學生餓肚子，以及方便他們為每一個學生製作餐點，每一份餐點的量都會相同，然而一份餐點對於某些學生來說太少，因此必須多跑幾次餐廳才能吃飽，已知每位學生不會跑大於 3 次餐廳，而每位學生只會吃自己所需要的份量，剩餘的份量就是浪費。

請最小化 ax + by，其中 a, b 為給定的常數，x 為所有學生所製造的廚餘，y 為所有學生跑餐廳次數的總和。

引用自：UVa 11633 - Food portion sizes | Morris Blog

Input： 每組測資第一個數字 N，表示有幾位學生，後面兩個整數分別代表 a、b，之後 N 個整數表示每位學生的食量。

Output： 輸出 ax + by 的最小值，若不為整數，請輸出為約分後的分數型態。

解題思路

由於輸出格式的原因，所以要避免再計算的時候出現小數，因此先將所有學生的食量都乘以 6，因為每位學生可能會去餐廳 1 ~ 3 次，這樣每份餐點的量就會是整數。

之後暴力法模擬每位學生去餐廳 1 ~ 3 次的情況下每份餐點的量，計算出 ax + by 的值即可，需要注意的是，因為我們把每位學生的食量都乘以 6，因此拿取的次數也要先乘以 6，這樣 ax + by 的值即是我們計算出的結果除以 6。

最後再檢查結果是否有分數，若有分數則找出該值與 6 的最大公因數，之後輸出即可。

參考解法

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;

// reference: https://ppt.cc/fOSfWx

static auto __ = []
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

int GCD(int x, int y)
{
    if (y % x == 0) return x;
    return GCD(y % x, x);
}

int N;
int a, b;
int mx;
int stus[1001];

void init()
{
    mx = INT_MIN;
}

void read()
{
    cin >> a >> b;
    for (int i = 0; i < N; ++i) cin >> stus[i], mx = max(mx, stus[i] *= 6);
}

void solve()
{
    int x, y;
    int mn = INT_MAX;
    int q1, q2; // 餐點量

    for (auto& time : { 1, 2, 3 }) for (int i = 0; i < N; ++i)
    {
        // 有學生需要跑餐廳超過三次
        if ((q1 = stus[i] / time) * 3 < mx) continue;

        x = y = 0;
        for (int j = 0; j < N; ++j)
        {
            q2 = stus[j];
            while (q2 > q1) q2 -= q1, ++y;
            x += q1 - q2;
            ++y;
        }

        mn = min(a * x + 6 * b * y, mn);
    }

    // 約分
    int _gcd = GCD(mn, 6);
    if (_gcd == 6) cout << mn / 6 << '\n';
    else cout << mn / _gcd << " / " << 6 / _gcd << '\n';
}

int main()
{
    while (cin >> N && N)
    {
        init();
        read();
        solve();
    }
}

參考資料

UVa 11633 - Food portion sizes | Morris Blog