UVA.11384 Help is needed for Dexter (思维题)
2024-09-01 06:55:39
UVA.11384 Help is needed for Dexter (思维题)
题意分析
同样水题一道,这回思路对了。
给出数字n,面对一个1,2,3,4……n的数字序列,你可以对他们的部分或者全部减去一个相同数字,最后使得这个序列变为全0的序列,求这样操作的次数最小值。
一开始着手想的是两两分组,既然能两两分组,为什么不三三分组呢?既然能三三分组,为什么不能四四分组呢?不难联想到二分法,即折半分组,看如下的例子:
n = 9
1,2,3,4,5,6,7,8,9
折半后
1,2,3,4
5,6,7,8,9
使5到9均减5,便得到
1,2,3,4
0,1,2,3,4
好了就有2个1234的序列了,再次折半,变成:
1,2,1,2
3,4,3,4(那个0已经省略了),然后对下面的序列全部减2,就会得到。
1,2,1,2
1,2,1,2
然后再折半,把所有的2全部减1,即得到:
1,1,1,1,1,1,1,1
最后一步,所有的1都减去1,变成0了。
根据上述的思路,可以看出,每一次折半,都要进行一次减法操作,那么我们不难想到这样一个算法:每次都除2,除2的同时计数器+1,知道算到1为止。
代码总览
#include <iostream>
#include <cstdio>
using namespace std;
int f(int n)
{
return n == 1 ? 1 :f(n/2) +1;
}
int main()
{
int n;
while(scanf("%d",&n)!= EOF){
int ans = f(n);
printf("%d\n",ans);
}
return 0;
}
最新文章
- 【原】AFNetworking源码阅读(四)
- android基础知识进阶
- CentOS6.3安装MongoDB2.2 及 安装PHP的MongoDB客户端
- A Xamarin.Forms Infinite Scrolling ListView
- 谢谢博客-园,让我不再有开源AYUI的想法
- Java for LeetCode 046 Permutations
- 【wikioi】2800 送外卖(状压dp+floyd)
- (十)makefile
- Oracle连接的若干错误
- oralce 函数 FOR windows 跟踪神器
- 考上好大学,然后进入IT行业是穷人孩子晋级中产的唯一出路?
- Tkinter教程之Button篇(1)
- LINUX C++ 技术博客
- uboot下 Nand flash 启动 内核与根文件系统
- css(html)背景图优化合并
- 给我的cnblogs主页做一个响应式布局模板
- 独立游戏《Purgatory Ashes》的经验与总结
- float数组转字符串实施方案小记
- CSS粘住固定底部的5种方法
- 2019清明期间qbxt培训qaq
热门文章
- ThinkPHP开启设置子域名笔记
- springboot在application.yml中使用了context-path属性导致静态资源法加载,如不能引入vue.js,jquery.js,css等等
- 第5章 Linux网络编程基础
- Redis 数据结构服务器
- CDH/Hadoop 5.15 installation steps
- leetcode个人题解——#19 Remove Nth Node From End of List
- leetcode个人题解——#18 4sums
- Python3 Tkinter-Message
- 编译安装hadoop2.6.3
- The Uncle_b&#39;s First Love