GCJ 2015 – Qualification Problem B – Infinite House of Pancakes (无尽馅饼屋) – 解题报告

第二题:无尽馅饼屋 / Infinite House of Pancakes

Google Code Jam 2015 比赛记录:http://www.huangwenchao.com.cn/2015/04/gcj-2015-qual.html

有一个无尽馅饼屋,僧多肉少,有限的饼,无限的食客。

开始时,有 D 个食客手上的盘子有饼,分别有 Pi 个饼,其他食客的盘子没有饼。

正常的话,每分钟,盘子里有饼的食客会吃掉他们盘子里面的一个饼。

另外有一些特殊时间(一分钟为单位),大家不吃东西,管理员会选取其中一个非空盘子,然后从里面拿一些饼放到另一个食客的盘子里(目标盘子可以有饼,也可以没饼)。

现在你是管理员,每一分钟你都可以选择:

  1. 让大家吃
  2. 执行一个特殊时间方案

问:大家最快需要多少分钟才能吃完?


解题报告:

定理一:结果不会超过 max(P),即不会超过最多的盘子里面的饼数

显然,管理员睡大觉不分配,让他们一开始就吃,结果就是这个。

定理二:如果要分配肯定先分配完再吃

这个也是显然的,同样的分配方式先吃再分的时间肯定大于等于先分再吃。

定理三:可以用每次分配出来一个固定块数达到最优,而且剩余块数小于等于这个固定的块数

比较拗口,翻译一下:

如果对 P[0..D] 这堆饼进行分配,分配出来 Q[0..E] 这一堆,剩下原来的 P'[0..D]

要证明,其中 Q[0..E] 全部都等于一个固定的 Z,而且 Z >= P'[0..D],这可以达到最优。

这个目前是直觉,证明还需思考。

结论:

OK,有了上述条件,我们就可以枚举这个固定的块数 Z,当然 Z < ans,因为分完还得吃。

枚举 Z 之后,我们就可以遍历一下 P,然后对于每个 x = P[i],将其分成不超过 Z 的块,需要 (x - 1) // Z 次。汇总一下即得分配的时间,加上 Z 作为吃的时间作为目标优化 ans 最终即可得到最优解。

例程:
for t in range(int(input())):

    D = int(input())

    P = list(map(int, input().split()))

    # 结果显然至多不会超过 max(P),也就是完全不分配的情况
    ans = max(P)

    # 遍历分配块的大小,然后最优化时间
    Z = 2
    while Z < ans:
        ans = min(ans, sum([(x - 1) // Z for x in P]) + Z)
        Z += 1

    print('Case #%d: %s' % (t + 1, ans))

原题内容:

题目链接:https://code.google.com/codejam/contest/6224486/dashboard#s=p0

Problem

At the Infinite House of Pancakes, there are only finitely many pancakes, but there are infinitely many diners who would be willing to eat them! When the restaurant opens for breakfast, among the infinitely many diners, exactly D have non-empty plates; the ith of these has Pi pancakes on his or her plate. Everyone else has an empty plate.

Normally, every minute, every diner with a non-empty plate will eat one pancake from his or her plate. However, some minutes may be special. In a special minute, the head server asks for the diners’ attention, chooses a diner with a non-empty plate, and carefully lifts some number of pancakes off of that diner’s plate and moves those pancakes onto one other diner’s (empty or non-empty) plate. No diners eat during a special minute, because it would be rude.

You are the head server on duty this morning, and it is your job to decide which minutes, if any, will be special, and which pancakes will move where. That is, every minute, you can decide to either do nothing and let the diners eat, or declare a special minute and interrupt the diners to make a single movement of one or more pancakes, as described above.

Breakfast ends when there are no more pancakes left to eat. How quickly can you make that happen?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each consists of one line with D, the number of diners with non-empty plates, followed by another line with D space-separated integers representing the numbers of pancakes on those diners’ plates.

Output

For each test case, output one line containing “Case #x: y”, where x is the test case number (starting from 1) and y is the smallest number of minutes needed to finish the breakfast.

Limits

1 ≤ T ≤ 100.

Small dataset

1 ≤ D ≤ 6. 1 ≤ Pi ≤ 9.

Large dataset

1 ≤ D ≤ 1000. 1 ≤ Pi ≤ 1000.

Sample
Input

3
1
3
4
1 2 1 2
1
4

Output 

Case #1: 3
Case #2: 2
Case #3: 3

In Case #1, one diner starts with 3 pancakes and everyone else’s plate is empty. One optimal strategy is:

Minute 1: Do nothing. The diner will eat one pancake.

Minute 2 (special): Interrupt and move one pancake from that diner’s stack onto another diner’s empty plate. (Remember that there are always infinitely many diners with empty plates available, no matter how many diners start off with pancakes.) No pancakes are eaten during an interruption.

Minute 3: Do nothing. Each of those two diners will eat one of the last two remaining pancakes.

In Case #2, it is optimal to let the diners eat for 2 minutes, with no interruptions, during which time they will finish all the pancakes.

In Case #3, one diner starts with 4 pancakes and everyone else’s plate is empty. It is optimal to use the first minute as a special minute to move two pancakes from the diner’s plate to another diner’s empty plate, and then do nothing and let the diners eat for the second and third minutes.


【转载请附】愿以此功德,回向 >>

原文链接:https://www.huangwenchao.com.cn/2015/04/gcj-2015-qual-b.html【GCJ 2015 – Qualification Problem B – Infinite House of Pancakes (无尽馅饼屋) – 解题报告】

《GCJ 2015 – Qualification Problem B – Infinite House of Pancakes (无尽馅饼屋) – 解题报告》有1个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注