upc 真假鉴定 思维+模拟
发布日期:2021-09-25 23:57:28
浏览次数:5
分类:技术文章
本文共 1486 字,大约阅读时间需要 4 分钟。
真假鉴定
时间限制: 1 Sec 内存限制: 128 MB题目描述
有n堆硬币依次排列,每一堆有a_i个。每堆硬币全是真币或全是假币,真币每个重5克,假币每个重4克。你有一台电子天平,可以从每堆硬币中挑出若干个进行一次称量(也可以一个都不选)。现在你想要知道,若要确定前1,2,……,n堆硬币的真假,至少要称量几次。 输入 第一行一个整数n,表示硬币的堆数。 接下来一行n个整数a_i,表示每堆硬币的数量。输出
n行,每行一个整数,第i行表示想要确定前i堆硬币的真假至少要称量几次。 样例输入 Copy 3 2 3 4 样例输出 Copy 1 1 1 提示对于10%的数据,n≤1
对于30%的数据,n≤2 对于60%的数据,n≤100 对于80%的数据,n≤1000 对于100%的数据,n≤10 ^ 5,a_i≤10 ^ 9 存在10%的数据,a_i=1请教大佬之后,终于搞懂了。
根据给出的提示,可以知道当拿出来的每个组的个数为 1 2 4 8 … 的时候就可以唯一确定,所以问题转换成前 i 个数中1 2 4 8 … 这样组合的最小组数。
思路就是枚举每一个数,找到 <= 当数的最大的2的幂,让这个位置的幂数加1,对当前位置及之前的数,依次枚举1-30(指的是2的幂的位置,比如说 2 ^ 0 的位数为1,2 ^ 3 的位数为4),每种分两种情况讨论: (1) 当当前的2的幂的个数 > 当前位数与方案数的乘积,说明方案数不够,需要添加方案,添加的方案为 多出来的个数 / 当前位数,当不能整除的时候,还需要多出来一个方案存多余的。 (2)反之则在当前方案后面加上即可。 对于 5 5 5 这种的,显然 5 可以表示成1 2 4 ,往前补位就好了,也就是说每次枚举到的位数,比如当前位数为4,前面需要构成能1 2 4 8 这样的数列,而且每一个数位一定可以放得下,因为枚举的方式是递增的。#include#include #include #include #include
转载地址:https://blog.csdn.net/DaNIelLAk/article/details/105401511 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
逛到本站,mark一下
[***.202.152.39]2024年03月14日 01时34分43秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
java 配置文件配置路径_Java读取配置文件路径设置
2019-04-21
vux 选择器_vue中的scoped分析以及在element-UI和vux中的应用
2019-04-21
java实验一目的_Java实验报告(实验一)
2019-04-21
php 内存泄露检测工具,php - 诊断内存泄漏 - 允许#bytes的内存大小耗尽
2019-04-21
Java 去除空格获取文件路径
2019-04-21
python 批量修改文件名称去除文件名中空格
2019-04-21
python 将文件名写入 txt文件
2019-04-21
python 3 读取文件txt 打印print
2019-04-21
python 查找txt文件中的字符串
2019-04-21
python 字符串替换 本地地址转换为网络地址
2019-04-21
Python3 http 服务任意目录 设定访问目录
2019-04-21
Python 移动鼠标到 句柄指定位置
2019-04-21
python窗口置顶 并输入中文
2019-04-21
Android studio 读取sd卡mp3 播放音乐
2019-04-21
Android studio 47 listview 处理单击和长按事件
2019-04-21
android studio 48 Android选项卡TabHost
2019-04-21
android studio 49自定义 ListView
2019-04-21
android studio 50
2019-04-21