首页 > 试题广场 >

训练部队

[编程题]训练部队

热度指数：1020 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

小牛牛是牛牛王国的将军,为了训练出精锐的部队,他会对新兵进行训练。部队进入了n个新兵,每个新兵有一个战斗力值和潜力值,当两个新兵进行决斗时,总是战斗力值高的获胜。获胜的新兵的战斗力值就会变成对手的潜力值 + 自己的战斗力值 - 对手的战斗力值。败者将会被淘汰。若两者战斗力值一样,则会同归于尽,双双被淘汰(除了考察的那个新兵之外，其他新兵之间不会发生战斗) 。小牛牛想知道通过互相决斗之后新兵中战斗力值+潜力值最高的一个可能达到多少,你能帮助小牛牛将军求出来吗?

输入描述:

输入包括n+1行,第一行包括一个整数n(1 ≤ n ≤ 10^5);
接下来的n行,每行两个整数x和y(1 ≤ x,y ≤ 10^9)

输出描述:

输出一个整数,表示新兵中战斗力值+潜力值最高的一个能达到多少。

示例1

输入

2
1 2
2 1

输出

算法知识视频讲解

Python

无瑕2017

要求：找出max(通过互相决斗之后新兵中战斗力值+潜力值).
获胜者战斗力 = (对手的潜力值 - 对手的战斗力值 )+ 自己的战斗力值 
max(战斗力 + 潜力) = (对手的潜力值 - 对手的战斗力值 )+ (自己的战斗力值 + 自己的潜力值)
第一部分保证为正直，即 对手的潜力值 >  对手的战斗力值

if 本人 自己的潜力值 < 自己的战斗力值: max(战斗力 + 潜力) = max(对手的潜力值 - 对手的战斗力值 ) + (自己的战斗力值 + 自己的潜力值)  保证max(自己的战斗力值 + 自己的潜力值) else:  max(战斗力 + 潜力) = max(对手的潜力值 - 对手的战斗力值 ) - (自己的潜力值 - 自己的战斗力值) + (自己的潜力值 + 自己的战斗力值) 
        = max(对手的潜力值 - 对手的战斗力值 )  + 2 * 自己的战斗力值
        保证 max(2 * 自己的战斗力值)

因此，求 max(自己的战斗力值 + 自己的潜力值)，max(2 * 自己的战斗力值)，max((对手的潜力值 - 对手的战斗力值 ),
max1 = max(对手的潜力值 - 对手的战斗力值 ) + max(自己的战斗力值 + 自己的潜力值)
max2 = max(对手的潜力值 - 对手的战斗力值 ) + max(2 * 自己的战斗力值) 最终结果：max(max1, max2)

#-*-coding:utf-8-*- n = int(raw_input())

lis = []
sum_zhan_qian = 0
max_zhan_qian = 0
max_zhan = 0
max_xin = 0

for i in xrange(0, n):
    temp = raw_input()
    [x, y] = map(int, temp.split())
    lis.append([x, y])
    if lis[i][0] < lis[i][1]:
        sum_zhan_qian = sum_zhan_qian + lis[i][1] - lis[i][0]
        temp = 2 * lis[i][0]
        if temp > max_zhan:
            max_zhan = temp
    else:
        temp = lis[i][0] + lis[i][1]
        if temp > max_zhan_qian:
            max_zhan_qian = temp

max_xin = sum_zhan_qian + max(max_zhan_qian, max_zhan)
print max_xin

发表于 2017-08-12 11:32:33 回复(0)