N 枚のカードがあります. i 枚目のカードには, aiという数が書かれています. Alice と Bob は, これらのカードを使ってゲームを行います. ゲームでは, Alice と Bob が交互に 1 枚ずつカードを取っていきます. Alice が先にカードを取ります. 2 人がすべてのカードを取ったときゲームは終了し, 取ったカードの数の合計がその人の得点になります. 2 人とも自分の得点を最大化するように最適な戦略を取った時, Alice は Bob より何点多く取るか求めてください.
制約
N は 1 以上 100 以下の整数
ai(1≤i≤N)は 1 以上 100 以下の整数
入力
入力は以下の形式で標準入力から与えられる.
N
a1 a2 a3 ... aN
出力
両者が最適な戦略を取った時, Alice は Bob より何点多く取るかを出力してください.
入力例 1
2
3 1
出力例 1
2
最初, Alice は 3 が書かれたカードを取ります. 次に, Bob は 1 が書かれたカードを取ります. 得点差は 3 – 1 = 2 となります.
入力例 2
3
2 7 4
出力例 2
5
最初, Alice は 7 が書かれたカードを取ります. 次に, Bob は 4 が書かれたカードを取ります. 最後に, Alice は 2 が書かれたカードを取ります. 得点差は, 7 – 4 + 2 = 5 点となります.
入力例 3
4
20 18 2 18
出力例 3
18
解答例
N = int(input())
cards = list(map(int, input().split()))
cards.sort(reverse=True)
alice_score = 0
bob_score = 0
for i in range(N):
if i % 2 == 0:
alice_score += cards[i]
else:
bob_score += cards[i]
print(alice_score - bob_score)
# 入力の受け取り
N = int(input())
a = list(map(int, input().split()))
# カードを降順にソート
a.sort(reverse=True)
# 得点の計算
alice_score = sum(a[i] for i in range(0, N, 2))
bob_score = sum(a[i] for i in range(1, N, 2))
# 結果の出力
print(alice_score - bob_score)
コメント