[AtCoder] [經典競程 90 題] 024 - Select +/- One(★2)

題目連結:https://atcoder.jp/contests/typical90/tasks/typical90_x
題目大意:
給定兩個序列 $A$, $B$,每次操作可以把$A$中任意元素$A_i$變成$A_i-1$或$A_i+1$,問可不可以恰$K$次後把$A$變成$B$。
隨手用python寫了一個XD
總之想法就是如果$A_i$比$B_i$小,那我們一定至少要花$B_i-A_i$次把$A_i$變成$B_i$,比較大的 case 也差不多,於是我們就有了一個基礎的下界$\sum |A_i-B_i|$,如果$K$比這個下界少,那一定不可能可以讓$A$跟$B$一樣。而若超過這個下界的話,實際上我們也可以透過一連串的$+1$跟$-1$操作來刻意浪費那些多出來的步數,所以再多判一下奇偶性就可以知道是不是一定可以有解了。(奇偶性一樣就可以靠前面說的方式構造,不同的話則因為我們每一步對應的奇偶性都是固定的,所以不同則一定構不出來)

n, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
s = 0
for i in range(n):
	s += abs(a[i] - b[i])
print("Yes" if s <= k and s % 2 == k % 2 else "No")

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology