GCJ 2015 – Qualification Problem A – Standing Ovation (观众起立) – 解题报告

第一题:观众起立 / Standing Ovation

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

大意,有演出,下面有很多观众。

然后每个观众有一个害羞值 Si (0 <= Si <= 9),代表这个观众当且仅当 Si 个观众鼓掌时,他才会鼓掌。

现在告诉你所有观众最高的害羞值 Smax,以及从 0 到 Smax 的害羞值有多少名观众。

例如有一行输入:

5 110011

说明最高的害羞值是 5。

第二个参数是个数字字符串,长度为 5 + 1 = 6,表示了害羞值为 0 到 5 的人数:

  • Si = 0 的有 1 人
  • Si = 1 的有 1 人
  • Si = 2 的有 0 人
  • Si = 3 的有 0 人
  • Si = 4 的有 1 人
  • Si = 5 的有 1 人

对于每项输入,要输出至少还要往里面加多少个观众(害羞值随你定),才能确保最终全部人都会起立鼓掌?


解题报告:

这是典型的一个贪心问题,只需要从小到大遍历一次害羞值即可。

遍历的时候,我们记录当前一共站起来 s 个人,然后我们另外叫了 ans 个人。

那么初始条件当然是 s = 0ans = 0

当我们遍历到害羞值为 i 的时候:

1. 如果已经站起来的人数 s 还没达到害羞值 i,那么需要另找 i-s 个人(当然找不害羞的人可以马上站起来的最省事):

if i > s:
    ans += i - s
    s = i

2. 上一步判别完之后,让害羞值为 i 的那 a[i] 个人站起来,加到 s 里面:

s += a[i]
例程(Python):
for t in range(int(input())):

    a = list(map(int, list(input().split()[1])))

    s = ans = 0

    for i in range(len(a)):
        if i > s:
            ans += i - s
            s = i
        s += a[i]

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

原题内容:

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

Problem

It’s opening night at the opera, and your friend is the prima donna (the lead female singer). You will not be in the audience, but you want to make sure she receives a standing ovation — with every audience member standing up and clapping their hands for her.

Initially, the entire audience is seated. Everyone in the audience has a shyness level. An audience member with shyness level Si will wait until at least Si other audience members have already stood up to clap, and if so, she will immediately stand up and clap. If Si = 0, then the audience member will always stand up and clap immediately, regardless of what anyone else does. For example, an audience member with Si = 2 will be seated at the beginning, but will stand up to clap later after she sees at least two other people standing and clapping.

You know the shyness level of everyone in the audience, and you are prepared to invite additional friends of the prima donna to be in the audience to ensure that everyone in the crowd stands up and claps in the end. Each of these friends may have any shyness value that you wish, not necessarily the same. What is the minimum number of friends that you need to invite to guarantee a standing ovation? Input

The first line of the input gives the number of test cases, T. T test cases follow. Each consists of one line with Smax, the maximum shyness level of the shyest person in the audience, followed by a string of Smax + 1 single digits. The kth digit of this string (counting starting from 0) represents how many people in the audience have shyness level k. For example, the string “409” would mean that there were four audience members with Si = 0 and nine audience members with Si = 2 (and none with Si = 1 or any other value). Note that there will initially always be between 0 and 9 people with each shyness level.

The string will never end in a 0. Note that this implies that there will always be at least one person in the audience.

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 minimum number of friends you must invite.

Limits

1 ≤ T ≤ 100.

Small dataset

0 ≤ Smax ≤ 6.

Large dataset

0 ≤ Smax ≤ 1000.

Sample
Input

4
4 11111
1 09
5 110011
0 1

Output 

Case #1: 0
Case #2: 1
Case #3: 2
Case #4: 0

In Case #1, the audience will eventually produce a standing ovation on its own, without you needing to add anyone — first the audience member with Si = 0 will stand up, then the audience member with Si = 1 will stand up, etc.

In Case #2, a friend with Si = 0 must be invited, but that is enough to get the entire audience to stand up.

In Case #3, one optimal solution is to add two audience members with Si = 2.

In Case #4, there is only one audience member and he will stand up immediately. No friends need to be invited.


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

原文链接:https://www.huangwenchao.com.cn/2015/04/gcj-2015-qual-a.html【GCJ 2015 – Qualification Problem A – Standing Ovation (观众起立) – 解题报告】

发表评论

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