♥POJ 1032-Parliament【数学】

╰+攻爆jí腚メ 2022-08-22 00:28 155阅读 0赞

Parliament

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;10000K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;18006</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;7620</td> 
  </tr> 
 </tbody> 
</table>

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

Sample Output

3 4

Source

[Northeastern Europe 1998][]

解题思路:

题目大意就是给你个数，你要把它拆成几个数，使得它们的乘积最大。拆成的每分大小都不一样。

所以记住每位相差为一时，乘积最大，对于一个数我们从2开始累加，比如7：2+3=5了不能再加了，剩余2。依然根据差一原则从后向前加到每个数上。（记住）

#include<stdio.h>
    int ans[10120];
    int main()
    {
    	int n;
    	while(scanf("%d",&n)!=EOF)
    	{
    		int cnt=0;
    		ans[++cnt]=2;
    		n-=2;
    		while(ans[cnt]<n)
    		{
    			int t=ans[cnt];
    			ans[++cnt]=t+1;
    			n-=ans[cnt];
    		}
    		for(int i=cnt;i>0;i--)
    		{
    			ans[i]+=(n+i-1)/i;
    			n=n-(n+i-1)/i;
    		}
    		for(int i=1;i<cnt;i++)
    		{
    			printf("%d ",ans[i]);
    		}
    		printf("%d\n",ans[cnt]);
    	}
    	return 0;
     }

[Northeastern Europe 1998]: http://poj.org/searchproblem?field=source&key=Northeastern+Europe+1998