ABC103 D - Islands War

提出

code: python

n, m = map(int, input().split())

ans = 0

# 端と端

解答

code: python

n, m = map(int, input().split())

ab.sort(key = lambda x:x1)

# print(ab)

# 1, 4], [2, 5 -> 1

# 3, 5], 4, 6, 2, 7, 1, 8, [7, 9 -> 2 7, 9までは4を壊せば遮断できる tmpは必ず増加していく

res = 1

# bi番目の島の西にかかる橋を壊すとして、tmp変数に壊した橋の位置を記憶

tmp = ab01 - 1

for i in range(m):

# tmpより東の位置がaiだった場合は、新たに橋を壊す必要があるので、resに1を足してtmpを更新

# biについてソート済みなのでtmpとaiを比較すれば必要性を判断することができる

if tmp < abi0:

res += 1

tmp = abi1 - 1

print(res)

テーマ

メモ