本文主要是介绍POJ 1032 / Northeastern Europe 1998 Parliament (贪心)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://poj.org/problem?id=1032
题意：把N个人分成若干组且每组人数不同，每天每组派一个人出来开会，并且每天开会的这群人不与前面的日子的开会人群不完全相同。
也就是说，求N1+N2+...+Nn=N，使N1,N2,...,Nn都不相等且他们的乘积最大。
思路：分的组越多乘积越大（在题意下ab>a+b）
则有分法：设有一连续递增序列为2,3,...,i，和sum<=n，则：
1.若剩余值（n-sum）等于i，则最后输出序列为：3,4,...,i,i+2，即将原最大序列每项加1，再将最后剩余的一个1加到最后一项上。
2.若剩余值（n-sum）小于i，则从序列的最大项i开始，从大到小依次将每项加1，直到剩余值用完。
分法合理性的证明：
首先说说连续，可以看到最后结果a[i]-a[i-1]<=2,也就是相邻两个数不能相差2以上，因为如果a[i]-a[i-1]=3，那么显然a[i-1]+1，a[i]-1也是满足要求的，且它们之间的乘积大于原来的，因此当相邻两个数相差>2时，总可以找到它们之间的两个数使得结果是更优的。
再来说说该序列必须以2或3开始，若序列第一项为5，则5=2+3，而2*3>5使得结果更优，对于大于5的第一项有类似结果。
再考虑4为第一项，根据前面的第一条，那么第二项只能为5或6.对于4，5可以分解为2，3，4使得结果更优。而对于4，6可以分解为2，3，5使得结果更优。因此可以看到该序列不可能是以大于3为开始的。
完整代码：
/*0ms,356KB*/#include<cstdio>int main()
{int n;scanf("%d", &n);int i = 2, sum = 0;while (sum + i <= n){sum += i;++i;}int diff = n - sum, j;if (diff == i - 1){for (j = 3; j < i; ++j)printf("%d ", j);printf("%d", j + 1);}else{for (j = 2; j < i - diff; ++j)printf("%d ", j);for (; j < i; ++j)printf("%d ", j + 1);//最后多一个空格不要紧}putchar(10);return 0;
}
这篇关于POJ 1032 / Northeastern Europe 1998 Parliament (贪心)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
