洛谷 P2320 [HNOI2006]鬼谷子的钱袋

---

题目：

传送门

---

题意：

现在有$n$n个金币，问我们怎么将它分成最少的袋子使得这些袋子内的金币可以组成任意的数
并且每个袋子内的金子数不能相同

---

分析：

我们可以用到分治的思想，我们将一个数可以分为$1—\frac{n}{2}$1—2n​和$\frac{n}{2}+1—n$2n​+1—n
这样就不难看出，后者的所有数都等于前者加上$\frac{n}{2}$2n​
若我们将这个数保存起来，后者就能由前者直接转化而来
我们可以尝试代入一些数值进去，帮助理解

---

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<map>
#include<queue>
#define LL long long 
using namespace std;
inline LL read() {
    LL d=0,f=1;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){d=d*10+s-'0';s=getchar();}
    return d*f;
}																	
int len=0,m[10000005];
int main()
{
	int n=read();
	while(n)
	{
		m[++len]=n/2+n%2;
		n/=2;
	}
	printf("%d\n",len);
	sort(m+1,m+1+len);
	for(int i=1;i<=len;i++) printf("%d ",m[i]); 
	return 0;
}