北大pku poj 1032 Parliament解题报告源代码
题目地址: [url]http://acm.pku.edu.cn/JudgeOnline/problem?id=1032[/url]
-----代码仅供参考学习-----
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 5022 Accepted: 2156
Description
New convocation of The Fool Land's Parliament consists of N delegates. According to the present regulation delegates should be divided into disjoint groups of different sizes and every day each group has to send one delegate to the conciliatory committee. The composition of the conciliatory committee should be different each day. The Parliament works only while this can be accomplished.
You are to write a program that will determine how many delegates should contain each group in order for Parliament to work as long as possible.
Input
The input file contains a single integer N (5<=N<=1000 ).
Output
Write to the output file the sizes of groups that allow the Parliament to work for the maximal possible time. These sizes should be printed on a single line in ascending order and should be separated by spaces.
Sample Input
7
Sample Output
3 4
Source
Northeastern Europe 1998
贴道值得研究的题吧，虽然有人给出了解法,也总结出很多规律,可还是没有看到很好的证明
大意是把整数N分成不相等的任意个整数,使这些数乘积最大
有人总结了一些规律:
1.1<a1
if a1=1, then a1(=1), a[t] together could be replaced by a[t]+1.
reason: a[t]+1>a[t]*1
----------------------------------------------------------------------------------------
2.to all i, 1<=a[i+1]-a<=2;
if some i make a[i+1]-a>2,
then a,a[i+1] together could be replaced by a+1,a[i+1]-1 together.
reason: a*a[i+1] < (a+1)*(a[i+1]-1)
(a+1)*(a[i+1]-1)=a*a[i+1]+a[i+1]-a-1
so a[i+1]-a-1>0 (* a[i+1]-a>2)
----------------------------------------------------------------------------------------
3. at MOST one i, fits a[i+1]-a=2
if i<j and a[i+1]-a=2 and a[j+1]-a[j]=2 then
a,a[j+1] could be replaced by a+1, a[j+1]-1
reason: a*a[j+1]< (a+1)*(a[j+1]-1)
so a[j+1]-a-1>0 (* a[j]-a>=1 a[j+1]-a[j]>=1 so a[j+1]-a>=2 )
----------------------------------------------------------------------------------------
4. a1<=3
if a1>=4, then a1,a2 together could be replaced by 2, a1-1, a2-1 together
reason: a1*a2< 2*(a1-1)(a2-1)
(a1-1)(a2-1)=a1*a2-a1-a2+1
so a1*a2>2*(a1+a2-1) (* a1>=4 and a2>=5)
----------------------------------------------------------------------------------------
5. if a1=3 and one i fits a[i+1]-a=2 then i must be t-1
if i<t-1 then a[i+2] could be replaced by 2, a[i+2]-2 together
reason: a[i+2]<2*(a[i+2])-4
so a[i+2]>4 (* a[1]=3 a[3]>=5 so a[i+2]>=5)
做法就是求出以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<stdio.h>
int main()
{
int i,n,t,s,f[61],a[62];
f[1]=2;a[1]=2;
scanf("%d",&n);if(n==5){ printf("2 3\n");return 0;}
i=2;
for(t=2;t<=60;t++) a[t]=t+1;
for(t=2;t<=60;t++) f[t]=f[t-1]+a[t];
while(1){ if(f>=n) break; i++;}
if(f>n)
{
s=n-f[i-1];
t=i-1;
while(s)
{
a[i-1]++;
i--;
if(i==1) i=t+1;
s--;
}
for(i=1;i<=t;i++) printf("%d ",a);
}
if(f==n)
{t=i;
for(i=1;i<=t;i++) printf("%d ",a);
}
return 0;
}