上傳作業:http://203.68.236.9/problem/b0021
UVa網址:https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=609
內容 :
有一個叫做傻人國的國家,他們的國會要召開新會期了。國會總共有N個議員。根據現行的法規議員們被分在不同的委員會(每個議員僅能待在一個委員 會),且每個委員會的人數均不相同。每天每一個委員會都需推派一名代表參加協調會,而且協調會每天的組成都需不同。國會只有在以上的條件成立之下才能運 作。
你的任務是寫一個程式來幫這些議員分組(總共分多少組,每個組多少人),使得國會能夠運作的天數最大。
輸入說明 :
輸入的第一列有一個整數代表以下有多少組測試資料。
每組測試資料一列,含有1個整數 N(5 <= N <= 1000)。
第一列與第一組測試資料以及各組測試資料間均有一空白列,請參考Sample Input。
輸出說明 :
對每組測試資料輸出一列,包含委員會的數目以及各委員會的人數,使得國會能夠運作的天數最大。各委員會輸出的順序按人數由小到大輸出。以第一組測試資料為例說明:31個委員共被分成6組,各組人數分別為2、3、5、6、7、8。
各組測試資料間亦請輸出一空白列,輸出格式請參考Sample Output。
範例輸入 :
3
31
5
8
範例輸出 :
2 3 5 6 7 8
2 3
3 5
提示 :
* Luck 貓翻譯
出處 :
ACM 668
解題策略
Greedy
將n切割成不同數字,且各數字的積最大
演算法
step1 k+1無法達到則結束
表示將n先分給2,3,4,5, ... ,k,若n-(2+3+...+k)<k+1則結束
step2 將剩餘n-(2+3+...+k)由k開始平均分給
k,k-1,k-2..2用完為止
step3 若還有剩餘,也只會剩一個,分給k(最後一位)
程式碼