切換
舊版
前往
大廳
主題

ZeroJudge - d118: 一串數字 解題心得

Not In My Back Yard | 2018-12-07 23:38:50 | 巴幣 0 | 人氣 243

題目連結:


題目大意:
給定一串數字(長度不超過 36, 000, 000 ),並給定一正整數N。

求在不更動員有數字串之給定順序之下,挑選 N 個數所組成的可能最大的數之值。



範例輸入:
987645821 6
123456789 8
95655645 1



範例輸出:
987821
23456789
9



解題思維:
以範例輸入的第一筆之 987645821 6 為例,藍色代表目前存取的數字,紫色代表目前已經選的數字:
987645821
首先,第一個數字為 9 ,先挑就對了。

987645821
再來是 8 ,沒有大於 9 ,所以也挑。

987645821
再來是 7 ,沒有大於 8 ,所以也挑。

987645821
再來是 6 ,沒有大於 7 ,所以也挑。

987645821
再來是 4 ,沒有大於 6 ,所以也挑。

987645821
再來是 5 ,大於 4 ,所以把已挑選的 4 替換成 5 。

987645821
再來是 8 ,大於 5 ,也大於 6 。雖然也大於 7 ,但是剩下的數字剛好可以填成長度為 6 的數字,所以剩下全挑。因此最終結果為:
987645821

以上,我們可以觀察出:
當目前的數字,大於目前挑的數字的尾端時,就刪掉最後面的數,重複此步驟直到不大於尾端數字。然後就接在後面。但是要注意剩下的數字之數量,倘若剩下的數字剛好可以填補剩下的空隙,就全部都挑。

然後判斷一下特殊狀況(要挑的數字長度大於給定的數字串之長度之類……)即可。




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

創作回應

胖胖貓
這題的討論區一頓亂噴,我以為是來亂的0.0
2018-12-08 01:08:05
Not In My Back Yard
研究了一下這題以前的提交狀況,發現很多 NA(score:100%)
代表這題當時應該出了難以通過的測資之類的(我猜很要壓秒才會過)

反正現在Zerojudge伺服器還蠻快的,不用怕XD
2018-12-08 19:21:56

更多創作