牛客网 - [北京信息科技大学第十一届程序设计竞赛]kotori和糖果(堆合并)
发布日期:2021-07-01 00:18:53
浏览次数:3
分类:技术文章
本文共 1148 字,大约阅读时间需要 3 分钟。
题目链接:
时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32768K,其他语言65536K 64bit IO Format: %lld题目描述
kotori共有n块糖果,每块糖果的初始状态是分散的,她想把这些糖果聚在一堆。但她每次只能把两堆糖果合并成一堆。
已知把两堆数量为a和b的糖果聚在一堆的代价是|a-b|。 kotori想知道,她把这n块糖果聚在一堆的最小代价是多少?输入描述
第一行是一个正整数T,代表数据组数。
第二行到第T+1行,每行一个非负整数n,代表kotori的糖果总数量。输出描述
每行一个整数,代表kotori需要花费的最小代价。
输入
2
5 6
输出
2
2
说明
n=5时,kotori可以这样聚集糖果:
1 1 1 1 1 2 1 1 1 2 2 1 2 3 5 每一步的代价分别是0,0,1,1,总代价为2。
备注
对于50%的数据,0<T≤100000, 0≤n≤100000
对于另外50%的数据,T=1, 0≤n≤1e18
解题思路
题意:合并,求最小代价值。
思路:将一个堆二分,递归求该堆合并的最小代价值。Accepted Code:
#includeusing namespace std;typedef long long ll;ll cnt[100005], n;ll slove(ll x) { if (x <= 100000) { if (cnt[x]) return cnt[x]; if (x < 2 || !(x & (x - 1))) return cnt[x] = 0; if (x & 1) return cnt[x] = slove(x >> 1) + slove((x >> 1) + 1) + 1; return cnt[x] = slove(x >> 1) << 1; } if (x < 2 || !(x & (x - 1))) return 0; if (x & 1) return slove(x >> 1) + slove(x >> 1 + 1) + 1; return slove(x >> 1) << 1;}int main() { int t; scanf("%d", &t); while (t--) { scanf("%lld", &n); printf("%lld\n", slove(n)); } return 0;}
转载地址:https://lzyws739307453.blog.csdn.net/article/details/94547547 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
初次前来,多多关照!
[***.217.46.12]2024年04月26日 01时38分08秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
[10] JMeter-察看结果树,你知道都有哪些功能吗?
2019-05-01
[11] JMeter-结果分析之聚合报告
2019-05-01
[12] JMeter-结果分析之图形图表
2019-05-01
[13] JMeter-详解JMeter参数化之CSV Data Set Config
2019-05-01
[14] JMeter关联-详解JMeter正则表达式提取器
2019-05-01
优化jmeter脚本
2019-05-01
Gradle基础使用总结1
2019-05-01
性能测试场景设置---不同场景下对应的jmeter脚本【不定时补充】
2019-05-01
登录oracle数据库时常用的操作命令整理
2019-05-01
微信小程序实现安卓机下拉不刷新,ios下拉刷新操作(自定义底部tab栏在安卓机下拉)
2019-05-01
小程序动态获取组件高度(自定义Tabbar的高度)
2019-05-01
如何是实现微信会员开卡组件中一个手机号绑定一个微信号(思路篇)
2019-05-01
has been blocked by CORS policy: Response to preflight request doesn‘t pass access control check 报错
2019-05-01
使用aspose.words 18.6实现pdf文档转换
2019-05-01
包机制介绍
2019-05-01
Java数组详解
2019-05-01
Java面向对象详解
2019-05-01
在Debian 8上使用Apt-Get安装Java
2019-05-01
vs中动态DLL与静态LIB工程中加入版本信息的方法
2019-05-01