[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")

留言

  1. The pay table will show you an inventory of all of the symbols used within the recreation and what they're worth when you're lucky sufficient to line them up. "Too-big wins have been shown to stop play because of|as a result of} it’s such an intense shift within the state of affairs that you’ll sort of pause, you’ll stop, you’ll take your cash and go away," says Schüll. Stretching out gameplay with minor rewards, Schüll says, "lets you get within the circulate of, one other little win, one other little win." Caesars Slots is intended for those 21 and older for amusement functions only and doesn't provide ‘real money’ playing, or a chance to win actual cash or 퍼스트카지노 actual prizes based on recreation play.

    回覆刪除

張貼留言

這個網誌中的熱門文章

[IOICamp] 最小公倍數問題

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

[TIOJ] 1209. 圖論 之 二分圖測試