POJ1032 Parliament

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

输入：N

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

Sample Input

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 = ;

     for (cnt = ; sum +  + cnt<= N; ++cnt) {

         sum += ( + cnt);

     }

     int left = N - sum;

     int p =  + cnt;

     while (left > ) {

         --p;

         --left;

     }

     if (p == ) {

         for (int i =; i <  + cnt; ++i) {

             cout << i << " ";

         }

         cout <<  + cnt << endl;

     } else if (p == ) {

         for (int i =; i <  + cnt; ++i) {

             cout << i << " ";

         }

         cout <<  + cnt << endl;

     } else if (p == cnt + ) {

         for (int i =; i <  + cnt; ++i) {

             cout << i << " ";

         }

         cout <<  + cnt << endl;

     } else {

         for (int i =; i <= p; ++i) {

             cout << i << " ";

         }

         for (int i = p + ; i < cnt + ; ++i) {

             cout << i << " ";

         }

         cout <<  + cnt << endl;

     }

     system("pause");

     return ;

 }

巴特西

POJ1032 Parliament

最新文章

热门文章