第十四届蓝桥杯大赛软件赛省赛Python 《三国游戏》

问题描述

问题类型

排序，贪心算法。

问题分析

当第i个事件发生时会分别让X，Y，Z增加Ai，Bi，Ci

即当某个事件发生时，三国各增加士兵数Ai，Bi，Ci。

如果X，Y，Z的其中一个大于另外两个之和，我们认为其获胜。

即当n个事件都确定了是否会发生后，存在X，Y，Z中任一大于另外两个之和，则有其中一个国家获胜。由于n个事件都有发生与不发生两种情况，所以最终的结果有2^n种情况，如果所有的情况都不能决出胜负，则输出-1；否则，在所有能够决出胜负的情况中选择事件发生数最多的。

由输入和输出格式知，输入第二行至第四行表示按照顺序每一次事件若发生（可能不发生）则增加的国家士兵数量，所以输入的第二至四行每一列表示各国在某一次事件发生时增加的士兵数量。

问题简化

由于各事件独立，不需要考虑事件发生的顺序，只需考虑事件最终发生与否。

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解 。在这个问题中，所要求的「最好选择」就是找出事件发生数最多的，如何才能让事件数达到最多呢？

假设X国获胜，那么在每一次事件发生时，我们总是选择X国与Y国和Z国士兵增加数量之差尽量大，即A[i] - (B[i] + C[i])尽量大，当事件数增加到X - (Y + Z) > 0（保证X国能获胜）时，事件数达到最大。对于另外两个国家同理。最终找出三国最终获胜的所有情况中事件发生数能够达到最大的即可。
如果在所有情况都无法满足某一国能够获胜，即所有事件不论最终发生与否，都无法决出胜负，则输出-1。

代码实现

n = int(input())
X = list(map(int, input().split()))
Y = list(map(int, input().split()))
Z = list(map(int, input().split()))


def maxEventsnum(X, Y, Z, count=n):
    max = []
    temp = 0#士兵数之差
    j = 0
    for i in range(0, n):
        max.append(X[i] - Y[i] - Z[i])
    max = sorted(max)#对max进行排序，从大到小依次添加，直至最后一个temp仍大于零
    while count:
        count -= 1
        if temp + max[count] <= 0:
            if count == n - 1:
                j = -1
                break
            else:
                break
        else:
            j += 1
            temp += max[count]
    return j


ans = max([maxEventsnum(X, Y, Z), maxEventsnum(Y, X, Z), maxEventsnum(Z, X, Y)])
print(ans)