TOJ 6265 Alice爸爸包花

输出

每组输出一行，为m个花束每个分别的个数。（Special Judge）

思路：
刚开始被题目吓住了，不知从何下手，想着该怎么分成m个组又要正好表达1~n。转念一想，数据保证一定存在答案，那我是否可以从最小需要分成多少组入手?要用较少的数去表达一个较大数，我想到了利用X进制去表示，每个花束为X进制的一个权值。粗略估计下同X进制表达1-n需要的权值的个数为(X-1)logX(n),对此式子求导后为ln(n) *(ln(X)-1+1/X)）/(lnX)^2,因为n>=1且x>=2，所以该式是递增的。因此用2进制表示是最优（可能不够严谨）。
对于q位2进制数，可以表示0~2^q-1。
因为用二进制表示是所用个数最少，所以不存在m=q,方便起见可以先把m束设为1然后再依次变成1、2、4……直到剩余的不够构成2下一个的幂次，然后把剩余的加在第m组就行了。

#include
using namespace std;
int main()
{int n,m,ans[1002],tmp,pos,item,yu;while(cin>>n>>m){item=1;pos=2;tmp=n;for(int i=1;i<=m;i++){tmp--;ans[i]=1;}while(tmp){if(tmp-item*2+1>=0){ans[pos++]+=item*2-1;tmp-=item*2-1;item*=2;}else break;}ans[m]+=tmp;for(int i=1;i<=m;i++)printf("%d%c",ans[i],i<m?' ':'\n');}return 0;
}

若有什么错误，欢迎指正^ _ ^ 。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！