題目： 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;
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
