2014-07-24

UVa 11633 - Food portion sizes

1. Problem
2. Input Specification
3. Sample Input
4. Sample Output
5. Solution

Problem

The university canteen does not want any student to leave the canteen hungry. Therefore, as long as a student is hungry, he can get another portion of food for free. The canteen uses a fixed food portion size, because it would take too much time to first ask a student how much food he wanted. It can happen that a student doesn’t finish his last portion of food and the remainder has to be thrown away.

To minimize costs, the manager of the canteen wants to determine a food portion size S such that the amount of food that is wasted is small, but also the number of times the students have to fetch another portion of food is not too big. Note that these two goals can be conflicting:

By choosing a very small food portion size, one does not waste food, but simultaneously the number of times the students have to fetch food is big.
By choosing a large food portion size, one can make sure each student has to fetch only one portion, but at the same time it may happen that a large quantity of food is wasted.

The manager of the canteen has collected data about how many units of food each student eats. The problem to be solved can now be formulated mathematically as follows: Let x be the amount of food that is wasted, and y the number of times the students go to fetch food. Then, the goal is to minimize a × x + b × y, where a, b are weights that represent the relative importance of the two opposing goals. Note that x and y depend on the food portion size S and the quantities of food each student eats. We impose the additional constraint that no student should have to go more than 3 times to fetch food.

Input Specification

The input file contains several test cases. Each test case starts with a line containing an integer n, (1 ≤ n ≤ 1000), the number of students eating in the canteen. The next line contains the values a and b (1 ≤ a, b ≤ 10). The third line of each test case consists of n integers y1, …, yn (1 ≤ yi ≤ 100), where yi is the amount of food student i eats. Input is terminated by n=0.
Output Specification

For each test case print one line containing the costs resulting from an optimal choice of the food portion size. Print each value as a reduced fraction. If the result is an integer, do not print the denominator 1. See the sample output for details.

Sample Input

Sample Output

1
2
3

35 / 2
154 / 3
9

Solution

題目描述：

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

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

題目解法：

由於可能跑 1, 2, 3 次，通分得到分母為 6，保證最小化一定通過某一個人的其中一種情況，窮舉每一個人跑餐廳的次數後，並且在合法的情況下 (所有人皆不大於 3 次。)，計算 $ax + by$ 的結果。

#include <stdio.h> 
#include <algorithm>
using namespace std;
int main() {
    int n, a, b;
    int v[1024];
    while(scanf("%d", &n) == 1 && n) {
        scanf("%d %d", &a, &b);
        
        int mx = 0;
        for(int i = 0; i < n; i++) {
            scanf("%d", &v[i]);
            v[i] *= 6; // v[i]/3, v[i]/2, v[i]/1
            mx = max(mx, v[i]);
        }
        
        int minCost = 0x3f3f3f3f;
        for(int i = 0; i < n; i++)  {
            for(int j = 1; j <= 3; j++) {
                int S = v[i]/j;
                int x = 0, y = 0;
                
                if(S * 3 < mx)	continue;
                
                for(int k = 0; k < n; k++) {
                    x += (S * (v[k]/S + (v[k]%S != 0)) - v[k]);
                    y += v[k]/S + (v[k]%S != 0);
                }
                if(a * x + 6 * b * y < minCost)
                    minCost = a * x + 6 * b * y;
            }
        }
        if(minCost%6 == 0)
            printf("%d\n", minCost /6);
        else {
            int div = 6, g = __gcd(minCost, div);
            div /= g, minCost /= g;
            printf("%d / %d\n", minCost, div);
        }
    }
    return 0;
}

Morris' Blog