Survive in the White Terror
Problem B: Survive in the White Terror
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 127 Solved: 31
[ Submit][ Status][ Web Board]
Description
In 1927~1949, the whole of China were enveloped in the white terror. Many revolutionary people were killed by the kuomintang reactionaries. N people wanted to fight back. They divide into several groups, and the size of each group are different from each other. Everyday, each group sent one people to a new work-group. The work-group has been guarded by reactionaries. So the composition of the work-group should be different each day. If not, the reactionaries will notice that the group has been shown before, and all of them will be arrested and killed.
Duncan is the leader of the people who fight against KMT. He wonders that how many people should contain each group in order to make the work-group survive as long as possible. Can you help him?
Input
Each line of the input contains a single integer N (3<=N<=1000), terminated by EOF.
Output
For each input, write to the output file the sizes of groups that allow the work-group to survive maximal possible time. These sizes should be printed on a single line in ascending order and should be separated by a space.
Sample Input
7
10
Sample Output
3 4
2 3 5
题意：
现在有Ｎ个士兵，将它们进行分组，每个组的人数互不相同。每一天每个组将派一名士兵去一个新的组，每个组的组成每天都必须不一样，不然将会被国民党全部杀害，
现在，如果要经可能生存较长的时间，改怎样对这批士兵进行分组。
题意转化：
比如一个组有Ｍ个人，另一个组有Ｎ个人，每次派一个人去另一个组，这样便有Ｍ*N中组合方法。要想生存的更长，那就必须满足这种组合方式最多。
该题就能转化为：将Ｎ拆分成互不相同的数，使得它们的乘积最大。
解题思路：
把自然数N分解成若干个互不相同的正整数，使乘积最大； 题意挺晦涩的，就是说要维持这个会议召开需要满足几个条件，而要会议召开最久需要这个条件尽可能久的维持 接着就需要了将整数N分解任意个不同的整数，使这些整数的乘积最大 将N分解为N=a1+a2+a3+..+ak 可以归纳出这么一些规律 1.a1>1 如果a1=1，那么将a1加到ak上，必然使得到的这个乘积大于原来的乘积 2.2>=a[i+1]-a[i]>=1,因为如果出现>2,可以将a[i+1],a[i]改为a[i+1]-1,a[i]+1，使得到的乘积更大 3.最多只有一个i,使得a[i+1]-a[i]=2 反证法，假设i<j,并且a[i+1]-a[i]=2,a[j+1]-a[j]=2,那么将a[i],a[j+1]替换成a[i]+1,a[j+1]-1 将使得乘积更大 4.a1<=3 如果a1>=4,那么将a1,a2替换成2,a1-1,a2-1将使得乘积更大 5.如果a1=3,并且存在一个i使得a[i+1]-a[i]=2，那么i一定为t-1 做法就是求出以2起始的最大连续自然数序列之和sum，使得sum的值不超过输入数n， 然后分情况讨论： 设此最大序列为2、3、……、w，则： 1。若剩余值（n-sum）等于w，则最后输出序列为：3、4、……、w、w+2，即将原最大序列每项加1，再将最后剩余的一个1加到最后一项上。 2。若剩余值（n-sum）小于w，则从序列的最大项i开始，从大到小依次将每项加1，直到剩余值用完。
代码实现：
#include <iostream>
using namespace std;
int num[1000];
int main()
{
int N,sum,temp,l;
while(cin>>N)
{
if(N==3)
cout<<N/2<<" "<<N-N/2<<endl;
else if(N==4)
cout<<N/3<<" "<<N-N/3<<endl;
else
{
sum=l=0;
for(int i=2;i<=N;i++)
{
num[l++]=i;
sum+=i;
if(sum>N)
{
sum-=i;
l--;
temp=N-sum;
break;
}
}
for(int j=l-1;temp;temp--)
{
num[j]++;
j--;
if(j<0)j=l-1;
}
for(int i=0;i<l-1;i++)
cout<<num[i]<<" ";
cout<<num[l-1]<<endl;
}
}
}