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開始分配，使得每個數盡量靠近。

	#include <cstdio>
	using namespace std;
	int main()
	{
	int M,N;
	scanf("%d", &M);
	while (M--) {
	scanf("%d", &N);
	int ans[1001],nOfans = 0, sum = 0;
	for (int i = 2; sum + i <= N; i++){
	sum += i;
	ans[nOfans++] = i;
	}
	int left = N - sum;
	for (int i = nOfans-1; left > 0; i--, left--){
	if (i < 0) i = nOfans-1;
	ans[i]++;
	}
	printf("%d", ans[0]);
	for (int i = 1; i < nOfans; i++)
	printf(" %d", ans[i]);
	printf("\n");
	if (M) printf("\n");
	}
	return 0;
	}

view raw [UVa] 668 Parliament.cpp hosted with ❤ by GitHub