ABC138 C - Alchemist
備忘録
問題
回答
import sys import os def main(): if os.getenv("LOCAL"): sys.stdin = open("input.txt", "r") N = int(sys.stdin.buffer.readline().rstrip()) V = list(map(int, sys.stdin.buffer.readline().split())) V.sort() for n in range(N-1): V[n+1] = (V[n] + V[n+1])/2 print(V[N-1]) if __name__ == '__main__': main()
考え方
2個(x, y)
の食材を鍋に入れると(x + y) / 2 = (x/2 + y/2)
の価値になる。
仮にx = 100
とすると、1回の生成で100/2
、2回目の生成で100/4
となり、
他の食材と混ぜて別の食材に生成されるたびに、価値が半減していく。
そのため、価値の高い食材は最後に混ぜ、
価値の低い食材から他の食材と混ぜていくことで、最も高い価値を求めることが出来る。