Atcoder Problems という競プロを勉強する上でのコンテンツがあります。AtCoder Problems
今回は、hard100問の内、26問目を解説していきたいと思います。
問題名 【B – K個のケーキ】
考察
2日連続で食べる可能性が一番高いのは、一番個数の多いケーキです。
そのため、一番個数の多いケーキを配置し、その間にそれ以外のケーキを配置すれば同じケーキを連続で食べる可能性が低いです。
もし、
- 一番個数の多いケーキ <= それ以外のケーキ+1(両端の置くのでそれ以外のケーキが1個少なくてもok)
→0を出力 - 一番個数の多いケーキ > それ以外のケーキ+1
→max_cake – else_cake -1を出力
コード
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def II(): return int(sys.stdin.readline())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def S(): return sys.stdin.readline().rstrip()
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
K,T = MI()
A = LI()
max_cake = max(A)
else_cake = K - max_cake
if max_cake > else_cake+1:
print(max_cake - else_cake -1)
else:
print(0)
コメント