题目链接

题意概述:把正整数n分为m个正整数,m个正整数中不允许出现复数个非1的正整数,保证所有小于n的正整数都可以用一部分正整数的和表示,并且使m尽量小。

这道题不知道为啥bzoj上没有要求输出方案,导致我把bzoj的程序粘到洛谷上瞬间全wa。

思想还是非常简单的,第一个钱袋装n/2个金币,第二个装n/2/2个金币,第三个……

这样可以用和的形式表示任意小于n的正整数。

显然这样是最优解,而且基于不断除2得出的答案个数为log2n。

#include<cstring>
#include<iostream>
#include<cctype>
#include<cstdio>
#include<algorithm>
using namespace std;
inline int read()
{
register int X=;register char ch=;
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);ch=getchar()) X=(X<<)+(X<<)+ch-'';
return X;
}
inline void write(int x)
{
if(x>) write(x/);
putchar(x%+'');
}
int n,ans,b[],m;
int main()
{
n=read();
m=n;
while(m>>=) ans++;
m=ans+,ans=;
while(n)
{
b[m-(++ans)]=(n& ? (n>>)+ : n>>);
n>>=;
}
write(ans),putchar('\n');
for(int i=;i<ans;i++) write(b[i]),putchar(' ');
}

最新文章

  1. for循环后面跟分号 - for (i = 0; i &lt;= 3; i++);这不是错误语句
  2. Pair Project: Elevator Scheduler [电梯调度算法的实现和测试] --11061188刘强
  3. PHP正则表达式模式修饰符 /i, /is, /s, /isU等
  4. js jquery 实现点击按钮后,倒计时60秒才能再次点击发送验证邮件
  5. Install MongoDB driver for PHP on XAMPP for Mac OSX
  6. Objective-c归档的概念和用法
  7. JS 禁止浏览器右键菜单和刷新
  8. 服务确定撤销/删除/关闭 (ml81n)
  9. border-radius:50%和100%究竟有什么区别
  10. 如何为分布式系统优雅的更换RPC
  11. Mybatis 批量插入、批量更新
  12. Gathering Initial Troubleshooting Information for Analysis of ORA-4031 Errors on the Shared Pool
  13. VSCode插件开发全攻略(八)代码片段、设置、自定义欢迎页
  14. PAT甲级1068 Find More Coins【01背包】
  15. Android开发学习笔记(二)——编译和运行原理(1)
  16. ASP.NET MVC 4 简介
  17. 用C# 7.0的switch...case模式匹配取代一堆if语句
  18. HDU 4347 - The Closest M Points - [KDTree模板题]
  19. [POI2015]Trzy wieże
  20. functools.wraps 带参数的装饰器 多个装饰器装饰同一个函数

热门文章

  1. C# Mysql数据库备份、还原(MVC)
  2. Space Syntax(空间句法)
  3. php 安装imap报错“configure: error: utf8_mime2text() has new signature”解决
  4. python基础01day
  5. kylin Build过程问题排查:17 Step Name: Build Cube In-Mem
  6. 简要介绍Linux网络服务的种类
  7. 基于OpenGL的三维曲面动态显示实现
  8. 为什么K8s会成为主流?
  9. AI面试-算法结构基础
  10. ffmpeg 详解