深圳福永网站建设,龙华网站建设yihekj,微网站设计尺寸,外国可以做站外推广的网站题目
小蓝正在玩一款游戏。游戏中魏蜀吴三个国家各自拥有一定数量的士兵 X,Y,Z#xff08;一开始可以认为都为 0#xff09;。
游戏有 n个可能会发生的事件#xff0c;每个事件之间相互独立且最多只会发生一次#xff0c;当第 i个事件发生时会分别让 X,Y,Z 增加 A i , B…题目
小蓝正在玩一款游戏。游戏中魏蜀吴三个国家各自拥有一定数量的士兵 X,Y,Z一开始可以认为都为 0。
游戏有 n个可能会发生的事件每个事件之间相互独立且最多只会发生一次当第 i个事件发生时会分别让 X,Y,Z 增加 A i , B i , C i A_i,B_i,C_i Ai,Bi,Ci。
当游戏结束时 (所有事件的发生与否已经确定)如果 X,Y,Z的其中一个大于另外两个之和我们认为其获胜。 例如当 XYZ时我们认为魏国获胜。 小蓝想知道游戏结束时如果有其中一个国家获胜最多发生了多少个事件? 如果不存在任何能让某国获胜的情况请输出 −1。
输入格式 输入的第一行包含一个整数 n。 第二行包含 n个整数表示 A i A_i Ai相邻整数之间使用一个空格分隔。 第三行包含 n个整数表示 B i B_i Bi相邻整数之间使用一个空格分隔。 第四行包含 n 个整数表示 C i C_i Ci相邻整数之间使用一个空格分隔。
输出格式 输出一行包含一个整数表示答案。
数据范围 对于 40%的评测用例n≤500 对于 70%的评测用例n≤5000 对于所有评测用例 1 ≤ n ≤ 1 0 5 0 ≤ A i , B i , C i ≤ 1 0 9 1≤n≤10^50≤A_i,B_i,C_i≤10^9 1≤n≤1050≤Ai,Bi,Ci≤109。 注意蓝桥杯官方给出的关于 A i , B i , C i A_i,B_i,C_i Ai,Bi,Ci 的数据范围是 1 ≤ A i , B i , C i ≤ 1 0 9 1≤Ai,Bi,Ci≤10^9 1≤Ai,Bi,Ci≤109但是这与给出的输入样例相矛盾因此予以纠正。
输入样例 3 1 2 2 2 3 2 1 0 7 输出样例 2 样例解释 发生两个事件时有两种不同的情况会出现获胜方。 发生 1,2 事件时蜀国获胜。 发生 1,3 事件时吴国获胜。 代码(python版本)
nint(input())
def check(x,y,z)-int:w[]for i in range(n):w.append(x[i]-y[i]-z[i])w.sort(reverseTrue)res-1sum0for i in range(n):sumw[i]if sum0:resi1return res
alist(map(int,input().split()))
blist(map(int,input().split()))
clist(map(int,input().split()))
print(max(check(a,b,c),check(b,a,c),check(c,a,b)))代码cpp版本
代码先欠着思路 本题是一道贪心题。当我一开始看这个题目的时候首先想到的就是一道dfs题但是当我看到数据范围为 1 0 5 10^5 105的时候我直接人傻这还怎么dfs。于是换一个思路。 首先因为这个数据范围是 1 0 5 10^5 105,那么我们需要将时间复杂度控制在 n l o g n nlogn nlogn中。 本题要求的是一个国家打赢两个国家最多能发生多少次事件看到最多我就感觉是一道贪心题那么怎么贪心呢 首先我们需要想明白怎么贪那我们可以先假设三个国家分别是ABC然后我们假设 A B C ABC ABC,那么ABC到底是哪三个国家呢这个直接可以枚举出来A是魏蜀吴三个其中之一剩下的B和C就是除了A以外的两个国家。 那么我们可以写一个函数来判断 A B C ABC ABC最多能要多少次 那么我们可以遍历ABC三个数组然后用一个数组W来接受一下A国和BC国的兵力差也就是W[i]A[i]-B[i]-C[i]的值那么W[i]的含义是什么呢很明显当W[i]0的时候说明A的兵力比BC的要多这个事件我们当然要选。然后进行排序接下来就是每次都获取到当前的兵力。然后用一个sum来记录sum代表的是什么意思呢就是A当前比BC多sum个兵然后我们依次进行遍历sum不断累加W[i]当sum累加当前的兵力之后还是大于零说明当前的事件容许发生这时候就该让res了。直到sum小于0的时候就不行了。 然后我们来看这个思路整个的时间复杂度正好是 n l o g n nlogn nlogn(sort的时间复杂度)。 最后我们只需要调用上面的函数三次即可也就是check(魏蜀吴)check(蜀魏吴)check(吴蜀魏)然后三者取最大值就行。
