# 題目: UVa 11633 - Food portion sizes
# 題目說明
大學學生餐廳不希望任何學生離開餐廳時沒吃飽
所以只要學生的肚子還餓,他就能免費拿到另一份餐點
為了節省時間,學生餐廳統一了每份餐點的份量,但這會導致浪費的發生
給兩個常數 a
及 b
,你需要找到 a * x + b * y
的最小值
x
為浪費的餐點量y
為學生領餐的次數
INPUT:
每筆資料第一行有一個整數 N
,代表學生的數量
下一行有兩個整數 a
與 b
接下來有 N
個整數,代表每個學生吃的份量
當 N = 0
時結束程式
OUTPUT:
輸出 a * x + b * y
的最小值
如果為分數需要分開輸出
例如 17.5
輸出為 35 / 2
# 解題方法
- 由於可能跑
1、2、3
次,通分為 6,所以先將所有輸入乘以 6 儲存,並找出最大值 - 窮舉所有符合條件的可能 (不取餐超過 3 次),依序計算
x、y
次數 - 將最小的
a * x + b * y
紀錄,最後輸出
# 參考程式碼
#include <iostream> | |
#include <vector> | |
#include <climits> | |
using namespace std; | |
int main() | |
{ | |
// fast io | |
ios::sync_with_stdio(false); | |
cin.tie(nullptr); | |
cout.tie(nullptr); | |
int N, a, b, x; | |
while (cin >> N, N) | |
{ | |
// init | |
vector<int> student; | |
int maxn = 0; | |
pair<int, int> minn = { INT_MAX, 1 }; | |
// store data | |
cin >> a >> b; | |
for (int i = 0; i < N; ++i) | |
{ | |
cin >> x; | |
student.emplace_back(x * 6); | |
maxn = max(maxn, x * 6); | |
} | |
// run all posible of n | |
for (int div = 1; div <= 3; ++div) for (auto& i : student) | |
{ | |
int s1 = i / div; | |
int x = 0, y = 0; | |
if (s1 * 3 < maxn) continue; | |
for (auto& j : student) | |
{ | |
int s2 = j; | |
while (s1 - s2 < 0) s2 -= s1, ++y; | |
x += (s1 - s2); | |
++y; | |
} | |
minn = min(minn, { x * a + y * b * 6, div }); | |
} | |
auto& [i, j] = minn; | |
if (i % 6 == 0) cout << i / 6; | |
else cout << i * j / 6 << " / " << j; | |
cout << "\n"; | |
} | |
return 0; | |
} |
# 參考資料
https://morris821028.github.io/2014/07/24/oj/uva/uva-11633/