網頁

2014年2月7日 星期五

UVa 668 Parliament

本題連結
題意:
  議會中有N位代表,依照規定須分成好幾個group,每個group的人數不能一樣,然後每個group每天要派出1個人出席會議,每次的會議人員組成必須與以前不同,否則會議無法開始(意即每次組合不能與以前重複),求如何分配group人數使得能開會議的天數最久。
  本題簡而言之,即為給定整數N,把N分成a,b,c....不同數字,求乘積最大的方式。

想法:
  把數字分配的越小(試想如果每個group人數能一樣,那每組分成2或3乘積為最大)和越鄰近越好(如2,3,4,5..)。因此就從2開始,2,3,4,5,.....k,直到剩下的數left(=N-(1+2+3+...+k)) < (k+1)為止,那麼將left從k,k-1....往下分配,把每個數+1,如果分配到2如果left還有剩,再從k+1開始分配,使得每個數盡量靠近。