QOJ.ac

QOJ

実行時間制限: 1 s メモリ制限: 128 MB 満点: 100

#3120. 食物份量大小

統計

大学食堂不希望任何学生饿着肚子离开。因此,只要学生还没吃饱,他就可以免费再领取一份食物。食堂采用固定的食物份量,因为询问每个学生想要多少食物会耗费太多时间。有时学生可能吃不完最后一份食物,剩下的部分就必须被丢弃。

为了降低成本,食堂经理想要确定一个食物份量 $S$,使得浪费的食物总量较小,同时学生领取食物的次数也不会太多。请注意,这两个目标可能存在冲突:

  • 选择非常小的食物份量,可以避免浪费食物,但学生领取食物的次数会很多。
  • 选择较大的食物份量,可以确保每个学生只需领取一次食物,但同时可能会浪费大量的食物。

食堂经理收集了每个学生食用的食物量数据。现在,该问题可以数学化表述如下:设 $x$ 为浪费的食物总量,$y$ 为学生领取食物的总次数。目标是最小化 $a \times x + b \times y$,其中 $a$ 和 $b$ 是代表两个对立目标相对重要性的权重。请注意,$x$ 和 $y$ 取决于食物份量 $S$ 以及每个学生食用的食物量。我们额外施加一个约束:任何学生领取食物的次数不得超过 $3$ 次。

输入格式

输入文件包含多个测试用例。每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 1000$),表示在食堂用餐的学生人数。第二行包含权重 $a$ 和 $b$ ($1 \le a, b \le 10$)。每个测试用例的第三行包含 $n$ 个整数 $y_1, \dots, y_n$ ($1 \le y_i \le 100$),其中 $y_i$ 表示第 $i$ 个学生食用的食物量。输入以 $n=0$ 结束。

输出格式

对于每个测试用例,输出一行,包含选择最优食物份量后产生的成本。将每个值打印为最简分数。如果结果为整数,则不要打印分母 1。详情请参考样例输出。

样例

样例输入 1

5
1 1
3 7 1 9 12
3
10 1
11 13 17
2
2 3
6 3
0

样例输出 1

35 / 2
154 / 3
9

说明

在第一个样例输入中,最优的食物份量是 4.5。注意,食物份量为 3 时会产生 16 的更小成本,但第 5 个学生将不得不领取 4 次食物。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.