uva 668 - Parliament(贪心)

题目链接:uva 668 - Parliament


题目大意:给出一个n,问最多用几个不同的数组成n,如果有个数相同的,输出从小到大排序的字典序最大的。


解题思路:首先找到一个序列,由2+3+...+x是恰好小于n的,然后将n - sum(x)平局分给这若干个数。


#include <stdio.h>
const int N = 1005;

int sum(int x) {
	return (1 + x) * x / 2 - 1;
}

int main() {
	int cas, n;
	scanf("%d", &cas);
	while (cas--) {
		scanf("%d", &n);
		int num[N];
		for (int i = 2; i <= n; i++) if (sum(i+1) > n) {
			int s = (n - sum(i)) / (i - 1);
			int t = (n - sum(i)) % (i - 1);

			for (int j = 2; j <= i - t; j++) num[j] = j + s;
			for (int j = i - t + 1; j <= i; j++) num[j] = j + s + 1;
			printf("%d", num[2]);
			for (int j = 3; j <= i; j++) printf(" %d", num[j]);
			printf("\n");
			break;
		}
		if (cas) printf("\n");
	
	}
	return 0;
}


uva 668 - Parliament(贪心)

上一篇:如果数据集为空,MySQL将返回默认值


下一篇:在论坛中出现的各种疑难问题:各种问题