POJ1032 Parliament

题目来源：http://poj.org/problem?id=1032

题目大意：给定一个正整数N(5<=N<=1000)，将N拆为若干个不同的数使得它们的乘积最大（找到一组互不相等，和为N，乘积最大的正整数）。

输入：N

输出：选择的数，升序输出。

---

Sample Input

7

Sample Output

3 4

---

假设不考虑拆成不等的数这个条件，那么依我们的经验应该是拆成相等的数乘积最大。加上这个条件之后，就应该是相邻的数乘积最大。那么给定一个N时，我们希望能将它拆为尽可能小的连续的数。而选择的数一定不能小至1，因为乘1不改变目标值，起不到作用纯属浪费。所以最好拆到2.当从2开始的序列累加和到某个数即将超过N时，停下，将剩下的数由高位向低位每个数的值增加1.剩余的数最多会把所有的数都加了1，还剩1个，（如果剩的比这还多，在开始从2往上累加时是不会停下来的，由数列求和公式可知。）若还剩1则再加到最的数上去。

//////////////////////////////////////////////////////////////////////////
//        POJ1032 Parliament
//        Memory: 280K        Time: 0MS
//        Language: C++        Result: Accepted
//////////////////////////////////////////////////////////////////////////

#include <iostream>

using namespace std;

int main() {
    int N;
    cin >> N;
    int cnt;
    int sum = 0;
    for (cnt = 0; sum + 2 + cnt<= N; ++cnt) {
        sum += (2 + cnt);
    }
    int left = N - sum;
    int p = 1 + cnt;
    while (left > 0) {
        --p;
        --left;
    }
    if (p == 0) {
        for (int i =3; i < 2 + cnt; ++i) {
            cout << i << " ";
        }
        cout << 3 + cnt << endl;
    } else if (p == 1) {
        for (int i =3; i < 2 + cnt; ++i) {
            cout << i << " ";
        }
        cout << 2 + cnt << endl;
    } else if (p == cnt + 1) {
        for (int i =2; i < 1 + cnt; ++i) {
            cout << i << " ";
        }
        cout << 1 + cnt << endl;
    } else {
        for (int i =2; i <= p; ++i) {
            cout << i << " ";
        }
        for (int i = p + 2; i < cnt + 2; ++i) {
            cout << i << " ";
        }
        cout << 2 + cnt << endl;
    }
    system("pause");
    return 0;
}