大家好，歡迎閱讀周末codeforces專題。

我們今天選擇的問題是contest 1419的C題，目前有接近8000的人通過了本題。今天這題的難度不大，但是真的很考驗思維，一不小心就會踩中陷阱，我個人覺得非常有意思，適合周末動動腦。

題目鏈接：//codeforces.com/contest/1419/problem/C

題意

有一個叫做Killjoy的特工發明了一種新型的冠狀病毒叫做Convid-2069，專門在codeforces平台上傳播。這種病毒通過rating傳播，只要兩個人的rating一樣並且其中一個感染了病毒，那麼另外一個也會被感染。

這個病毒一開始的時候只有Killjoy自己感染了，他一共和n個人有聯繫。由於codeforces會定期舉辦比賽，參加比賽會改變一個人的rating，由於codeforces的規則，導致所有參賽的人的rating變動的總量為0，也就是說有人升了一定會有人降，大家的總和保持不變。已知Killjoy自己不會參賽，請問最少需要多少次比賽可以將所有人都感染。

對於每一次比賽，可以不必所有人都參與，傳染的發生不需要時間，瞬間就可以傳染。很容易證明，我們一定可以在有限次比賽當中將所有人都感染。

樣例

首先輸入一個t表示測試數據的組數()，對於每一組數據第一行輸入兩個數，分別是n和x。n表示和Killjoy有接觸的人的數量，x表示Killjoy自己的rating，()。

第二行輸入n個整數，表示這n個人的rating。要求輸出一個整數，表示最少需要的比賽數量()。

題解

這道題的思路非常直接，沒什麼彎彎繞，我們只需要觀察一下樣例就可以了。樣例當中有三組數據剛好對應了三種情況。

我們先來看第一種情況：這n個人的rating都和x相等，那麼意味着我們不需要比賽，就可以把所有人都感染了。結果當然是0，這一種非常簡單，大家應該都可以想明白。

第二種情況也不難，第二種情況就是雖然大家的rating不全等於x，但是大家的總和等於x * n。也就是說rating大於x的減小到x，小於x的增加到x，剛好可以通過一次比賽讓大家全部被感染，那麼最終的答案就是1。這對應樣例當中的68， 70的情況，x=69，很明顯68的增加1，70的減去1，就可以都變成69。

前面兩種理清楚了，再來看第三種情況，第三種情況也就是前面兩種都不符合的情況。也就是我們通過一次比賽沒辦法讓大家都等於x，不過這並沒有什麼關係，因為題目當中並沒有限制rating的範圍。我們完全可以讓其中n-1個人全部變成x，由於要保證大家的rating變動之和等於0，所以讓最後一個人來完成平衡的角色。

也就是說通過一次比賽，我們可以讓n-1個人全部被感染，最後留下一個人。那麼不難想出，我們只需要再多用一個回合就可以了。再多一個回合，我們可以讓第n個人變成x，讓一個已經感染的人來完成平衡。那麼，我們用了兩個回合就完成了所有人的感染。

整理一下思路，其實這題分為三種情況，第一種情況是大家全部都等於x，答案是0。第二種情況是大家可以只需要一個回合就變成x，如果上面兩種情況都不滿足的話，就額外再消耗一個回合即可。

這個思路也太簡單了，很快我就寫好了代碼：

import math
 
t = int(input())
 
for _ in range(t):
    n, x = list(map(int, input().split(' ')))
    arr = list(map(int, input().split(' ')))
 
    diff = 0
    sdiff = 0
    for i in range(n):
        diff += abs(arr[i] - x)
        sdiff += arr[i] - x
 
 # 如果所有人都等於x，那麼會在一開始就被感染完
    if diff == 0:
        print(0)
    # 如果可以通過一個回合讓所有人的rating調整到x，那麼只需要一個回合
    elif sdiff == 0:
        print(1)
    else:
        print(2)

但是很遺憾，當我提交了之後，並沒有AC，而是錯在了第二組數據。我想了很久，才終於想到了其中的trick。我先不說，大家先思考一下，看看能不能想到。

準備好了嗎？

我們剛才列舉的三種情況是沒有問題的，但是我們遺漏了一種。就是這一開始的n個人當中，可能有人的rating就等於x，所以他會在第一次比賽之前就感染。我們再想想最後一種情況，我們先把n-1個人的rating調整到x，再把調整當中付出的代價交給其中一個人來承擔。這也是我們需要第二個回合的原因，如果這n個人當中存在有人在開始之前就感染了，那麼我們完全可以讓這個已經感染的人來承擔代價，這樣我們就可以減少一個回合。

體現在代碼當中，就是我們需要額外增加一個判斷條件，判斷一下這n個人當中是否存在有人的rating等於x，會在一開始的時候就被感染。如果有的話，答案就是1。

附上代碼：

import math

t = int(input())

for _ in range(t):
    n, x = list(map(int, input().split(' ')))
    arr = list(map(int, input().split(' ')))

    diff = 0
    sdiff = 0
    flag = False
    for i in range(n):
        if arr[i] == x:
            flag = True
        diff += abs(arr[i] - x)
        sdiff += arr[i] - x

    if diff == 0:
        print(0)
    # 如果存在人感染，也只需要一個回合就可以完成感染
    elif sdiff == 0 or flag:
        print(1)
    else:
        print(2)

這道題其實並不難，但是很容易漏掉這種情況，這也是codeforces當中題目的魅力所在，考驗我們思維的縝密與細緻程度。我個人覺得還是非常有趣的，值得一做。

今天的文章就到這裡，衷心祝願大家每天都有所收穫。如果還喜歡今天的內容的話，請來一個三連支持吧~（點贊、關注、轉發）

原文鏈接，求個關注

本文使用 mdnice 排版

– END –