三国游戏（第十四届蓝桥杯）

本文介绍: 小蓝正在玩一款游戏。游戏中魏蜀吴三个国家各自拥有一定数量的士兵 X,Y,Z（一开始可以认为都为 0）。游戏有 n个可能会发生的事件，每个事件之间相互独立且最多只会发生一次，当第 i个事件发生时会分别让 X,Y,Z增加AiBiCi。当游戏结束时 (所有事件的发生与否已经确定)，如果 X,Y,Z的其中一个大于另外两个之和，我们认为其获胜。例如，当 X>Y+Z时，我们认为魏国获胜。小蓝想知道游戏结束时如果有其中一个国家获胜，最多发生了多少个事件?

题目

小蓝正在玩一款游戏。游戏中魏蜀吴三个国家各自拥有一定数量的士兵 X,Y,Z（一开始可以认为都为 0）。

游戏有 n个可能会发生的事件，每个事件之间相互独立且最多只会发生一次，当第 i个事件发生时会分别让 X,Y,Z
增加

A_i,B_i,C_i

$A_{i}, B_{i}, C_{i}$ 。

当游戏结束时 (所有事件的发生与否已经确定)，如果 X,Y,Z的其中一个大于另外两个之和，我们认为其获胜。
例如，当 X>Y+Z时，我们认为魏国获胜。
小蓝想知道游戏结束时如果有其中一个国家获胜，最多发生了多少个事件?
如果不存在任何能让某国获胜的情况，请输出 −1。

输入格式
输入的第一行包含一个整数 n。
第二行包含 n个整数表示

A_i

$A_{i}$ ，相邻整数之间使用一个空格分隔。
第三行包含 n个整数表示

B_i

$B_{i}$ ，相邻整数之间使用一个空格分隔。
第四行包含 n 个整数表示

C_i

$C_{i}$ ，相邻整数之间使用一个空格分隔。

输出格式
输出一行包含一个整数表示答案。

数据范围
对于 40%的评测用例，n≤500；
对于 70%的评测用例，n≤5000；
对于所有评测用例，

≤

，

≤

1≤n≤10^5，0≤A_i,B_i,C_i≤10^9

$1 \leq n \leq 1 0^{5} ， 0 \leq A_{i}, B_{i}, C_{i} \leq 1 0^{9}$ 。
注意，蓝桥杯官方给出的关于

A

i

,

B

i

,

C

i

A_i,B_i,C_i

$A_{i}, B_{i}, C_{i}$
的数据范围是

1

≤

A

i

,

B

i

,

C

i

≤

1

0

9

1≤Ai,Bi,Ci≤10^9

$1 \leq A i, B i, C i \leq 1 0^{9}$ ，但是这与给出的输入样例相矛盾，因此予以纠正。

输入样例：

3
1 2 2
2 3 2
1 0 7

输出样例：

2

样例解释

发生两个事件时，有两种不同的情况会出现获胜方。
发生 1,2 事件时蜀国获胜。
发生 1,3 事件时吴国获胜。

代码(python版本)

n=int(input())
def check(x,y,z)->int:
    w=[]
    for i in range(n):
        w.append(x[i]-y[i]-z[i])
    w.sort(reverse=True)
    res=-1
    sum=0
    for i in range(n):
        sum+=w[i]
        if sum>0:
            res=i+1
    return res
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
print(max(check(a,b,c),check(b,a,c),check(c,a,b)))

代码（cpp版本）

代码先欠着

思路：
本题是一道贪心题。当我一开始看这个题目的时候，首先想到的就是一道dfs题，但是当我看到数据范围为

10^5

$1 0^{5}$ 的时候我直接人傻，这还怎么dfs。于是换一个思路。
首先因为这个数据范围是

10^5

$1 0^{5}$ ,那么我们需要将时间复杂度控制在

nlogn

$n l o g n$ 中。
本题要求的是一个国家打赢两个国家最多能发生多少次事件，看到最多，我就感觉是一道贪心题，那么怎么贪心呢？
首先我们需要想明白怎么贪？那我们可以先假设三个国家分别是ABC，然后我们假设

A>B+C

$A > B + C$ ,那么ABC到底是哪三个国家呢？这个直接可以枚举出来，A是魏蜀吴三个其中之一，剩下的B和C就是除了A以外的两个国家。
那么我们可以写一个函数来判断

A>B+C

$A > B + C$ 最多能要多少次
那么我们可以遍历ABC三个数组，然后用一个数组W来接受一下A国和B+C国的兵力差，也就是W[i]=A[i]-B[i]-C[i]的值，那么W[i]的含义是什么呢？很明显当W[i]>0的时候说明A的兵力比B+C的要多，这个事件我们当然要选。然后进行排序，接下来就是每次都获取到当前的兵力。然后用一个sum来记录，sum代表的是什么意思呢，就是A当前比B+C多sum个兵，然后我们依次进行遍历，sum不断累加W[i]，当sum累加当前的兵力之后还是大于零，说明当前的事件容许发生，这时候就该让res++了。直到sum小于0的时候就不行了。
然后我们来看这个思路，整个的时间复杂度正好是