poj 1032 Parliament 数学

• 题目描述: http://poj.org/problem?id=1032
• 题目大意: 议会有N 个议员, 将他(她)们分成多组. 每次会议每组出一个代表, 且每次会议的代表都不完全相同. 求得一种分组情况, 使得能够开会的次数最多. 说白了就是求N 的一种划分 N = a1 + a2 + ... + a(t-1) + a(t), 使得M = a1 * a2 * ... * a(t - 1) * a(t) 最大.

关于该题的一些规则：

• 1.    1 < a1 < 4;
假设a1 = 1; 那么一个数乘以a1， 乘积并不变大， 还不如把a1 加给其他元素。
假设a1 >= 4;那么a1 可以划分为2 和 (a1 - 2), 2  * (a1 - 2) 一定大于a1.
• 2. 划分（假设升序）中，相邻元素只差最大为2， 这样的相邻对最多只有一对。
假设有a(k) - a(k - 1) > 2; 则这两个元素一定可以换成(a(k) + 1)   和   (a(k + 1) - 1), 使得乘积更大。所以相邻元素只差不大于2， 或是有且只有一对相邻元素只差为2。

假设有两对相邻元素只差等于2。 那么同样可以调整这4 个元素大小，使得乘积更大。

鉴于以上规律，对于该题给出以下解决方案：
假设sum( n ) 为整数从2 到n 的和, sum( i ) <= N, 且sum( i +　1 ) > N, t = N - sum( i );

• 如果t = i; 则把t 分成i 个1, 从2 到 i 这 i - 1 个元素分别加1, 最后剩下的一个1 加给最后一个元素. 所以, 最终序列为:3, 4, ... , i - 1, i, i + 2
• 如果t < i;则把t 分成t 个1, 分别加给从i 开始,往下的t 个元素. 所以最终序列为:
2, ... , (i - 2) + 1, (i - 1) + 1, i + 1.(从右到左有t 个加1项 )

#include <iostream>
using namespace std;

int main() {
	int n;
	while(cin>>n) {
		int i = 1;
		int sum = 0;
		while(sum + i + 1 <= n) {
			i++; 
			sum += i;
		}
		//cout<<i<<endl;
		int t = n - sum;
		if(i == t) {
			for(int j = 3; j <= i; j++)
				cout<<j<<" ";
			cout<<i + 2<<endl;
		}
		else if(t == 0) {
			int m = 2;
			while(m < i)
				cout<<m++<<" ";
			cout<<i<<endl;
		}
		else {
			int m = 2;
			while(m <= i - t)
				cout<<m++<<" ";
			m = i - t + 2;
			while(m <= i)
				cout<<m++<<" ";
			cout<<i + 1<<endl;
		}
	}
}