# 題目: UVa 11633 - Food portion sizes

# 題目說明

大學學生餐廳不希望任何學生離開餐廳時沒吃飽
所以只要學生的肚子還餓,他就能免費拿到另一份餐點

為了節省時間,學生餐廳統一了每份餐點的份量,但這會導致浪費的發生

給兩個常數 ab ,你需要找到 a * x + b * y 的最小值

  • x 為浪費的餐點量
  • y 為學生領餐的次數

INPUT:
每筆資料第一行有一個整數 N ,代表學生的數量
下一行有兩個整數 ab
接下來有 N 個整數,代表每個學生吃的份量
N = 0 時結束程式


OUTPUT:
輸出 a * x + b * y 的最小值
如果為分數需要分開輸出
例如 17.5 輸出為 35 / 2

# 解題方法

  1. 由於可能跑 1、2、3 次,通分為 6,所以先將所有輸入乘以 6 儲存,並找出最大值
  2. 窮舉所有符合條件的可能 (不取餐超過 3 次),依序計算 x、y 次數
  3. 將最小的 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/