Parliament

New convocation of The Fool Land‘s Parliament consists of N delegates. According to the present regulation delegates should be divided into disjoint groups of different sizes and every day each group has to send one delegate to the conciliatory committee. The composition of the conciliatory committee should be different each day. The Parliament works only while this can be accomplished.

You are to write a program that will determine how many delegates should contain each group in order for Parliament to work as long as possible.

Input 

Output 

Sample Input 

1

31

Sample Output 

2 3 5 6 7 8

思路：贪心，找一个2 + 3 + 4..+i的序列，使得最大小于n，然后剩下人数去补全，尽量平均补，如果不能平均剩下的就从后面往前补。

代码：

#include <stdio.h>
#include <string.h>

int t, n;

int Sum(int n) {
	return (1 + n) * n / 2 - 1;
}

void solve() {
	for (int i = 2; ; i++) {
		if (Sum(i + 1) > n) {
			int sum = Sum(i);
			int tmp = (n - sum) / (i - 1);
			int k = (n - sum) % (i - 1);
			int bo = 0, j;
			for (j = 2; j <= i -  k; j++) {
				if (bo++) printf(" ");
				printf("%d", j + tmp);
			}
			for (j = i - k + 1; j <= i; j++) {
				if (bo++) printf(" ");
				printf("%d", j + tmp + 1);
			}
			printf("\n");
			break;
		}
	}
	if (t) printf("\n");
}

int main() {
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		solve();
	}
	return 0;
}

UVA 668 - Parliament(贪心构造)

原文：http://blog.csdn.net/accelerator_/article/details/18240897