主題

ZeroJudge - f836: 卡片蒐集 解題心得

Not In My Back Yard | 2021-05-17 00:00:06 | 巴幣 0 | 人氣 64

題目連結:


題目大意:
輸入第一列給定一正整數 N (1 ≦ N ≦ 2 × 10 ^ 5),代表有 N 張卡片。接著的一列給定 N 個正整數(介於 1 ~ 10 ^ 9 之間),代表每張卡片上有的戰力值。

試問無法被給定的 N 張卡片之戰力值所湊出的最小的戰力值總和為多少?



範例輸入:
11
1 3 2 5 4 8 6 7 10 100 9


範例輸出:
56


解題思維:
先將給定的 N 張卡片之戰力值由小排到大,並命名為 B1 、 B2 、 …… 、 BN

假設我們已經知道我們可以湊到 0 ~ M - 1 的數字了,所以最小不能湊得的數字為 M,且此時我們正在看的數字為 Bi。接著我們判斷 M 與 Bi 的大小關係:
當 M ≧ Bi,可以看到 M - Bi < M (因為 Bi 至少為 1)且 0 ~ M - 1 的數字都是可以湊出的。因此我們現在可以湊出 M 了。同理,我們可以湊出 M + 1 、 M + 2 、 …… 、 M + Bi - 1。所以現在最小的不可湊出數字為 M + Bi

當 M < Bi,根據上面的論述,我們湊不出 M。而接下來的 Bi+1 、 Bi+2 等等皆大於等於 Bi ,所以就算考慮進接下來的數字同樣無法湊出 M 。

至於為何要排序呢?因為如果不排序,以上的論述將不成立:有可能考慮進較後面的數字反而可以湊得前面無法湊得的較小數字。而排序後便可以確保不管考慮到哪個數字,其所不能湊得的最小數字必定跟先前的一樣大或是更大。

而我們從 M = 1 以及 B1 開始執行以上程序,最後即可得出 B1 、 B2 、 …… 、 BN 無法湊出的最小之數字,即所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作