主題

ZeroJudge - f374: 分組 Grouping 解題心得

Not In My Back Yard | 2020-11-13 00:00:09

題目連結:


題目大意:
給定兩正整數 N 、 P (1 ≦ N ≦ 8, P 最多為一九位數數字且最左邊的位數不是「0」),代表一組要有 N 個人(編號最大的組別除外,可以不滿 N 個人)以及若干位選手將各自的戰力值(只會是 0 ~ 9 的數字,也就是每個位數代表一位選手)接在一起形成的數字。

分組方式為:
從 P 最右邊的位數開始往左,每 N 個人一組且依序編號為第 1 組、第 2 組、……。
測資保證會至少分出兩個組別。

求分組組別中戰力值總和最大的組別為何者?如果有多個戰力總和最大的,則輸出為組別編號最大的。



範例輸入:
範例輸入 #1
1 369

範例輸入 #2
2 193426

範例輸入 #3
5 10121315

範例輸入 #4
4 12344321


範例輸出:
範例輸出 #1
1 9

範例輸出 #2
3 10

範例輸出 #3
1 12

範例輸出 #4
2 10


解題思維:
因為是由右到左且每個位數代表一名選手的戰力值,因此我們可以對 P 除以 10 ,將 P 更新為商數並同時取其餘數 R (R 即是戰力值)。

每個組別做滿 N 次的除法運算(不論 P 剩下的位數是否滿 N 位),取得了 N 個餘數 R。將每一組的 N 個 R 值加總即是該組的戰力值總和。因此就與目前最大戰力值做比較,現在這個組別的戰力值總和若大於或等於當前最大戰力總和,則更新該最大之值並連同更新最大值發生之組別的編號。

最後輸出以上過程得到的最大值發生時的組別編號以及其最大戰力總和之值即可。




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

更多創作