前往
大廳
主題

ZeroJudge - c350: “綠白黃” 四校聯課 解題心得

Not In My Back Yard | 2021-04-13 00:00:16 | 巴幣 0 | 人氣 154

題目連結:


題目大意:
給定三正整數 N 、 K 、 W (N 、 K 、 W ≦ 10 ^ 4 且 W < K),代表一開始有 N 個電話號碼,每 K 個可以換 W 個新的電話號碼。用過的電話號碼不得再次使用。

試問最多可以得到多少電話號碼?



範例輸入:
// Example 1
6 5 1

// Example 2
144 188 87

// Example 3
9 3 2


範例輸出:
// Example 1
7

// Example 2
144

// Example 3
23


解題思維:
類似這題,但是這次不是每 K 個換 1 個而是 W 個。

不過同樣的論述依舊可以使用,根據該題的論述,我們可以額外換
floor((N - W) ÷ (K - W))
次電話。每次會有 W 組號碼,所以總共是
floor((N - W) ÷ (K - W)) × W
組額外的電話號碼。加上原本的 N 組之後,總計
N + floor((N - W) ÷ (K - W)) × W
此即為本題所求……不過還差一點,因為現在需要注意的是 N - W 可能不會 ≧ 0 了(不像該題)。

因此需要額外判斷 N - W < 0 的情況,對於該情況就只會得到一開始的 N 組號碼而已。




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

創作回應

更多創作