NC50038 kotori和糖果
2024-10-20 17:31:52
NC50038 kotori和糖果
题目
题目描述
kotori共有 \(n\) 块糖果,每块糖果的初始状态是分散的,她想把这些糖果聚在一堆。但她每次只能把两堆糖果合并成一堆。
已知把两堆数量为 \(a\) 和 \(b\) 的糖果聚在一堆的代价是 \(|a-b|\) 。
kotori想知道,她把这 \(n\) 块糖果聚在一堆的最小代价是多少?
输入描述
第一行是一个正整数 \(T\) ,代表数据组数。
第二行到第 \(T+1\) 行,每行一个非负整数 \(n\) ,代表kotori的糖果总数量。
输出描述
每行一个整数,代表kotori需要花费的最小代价。
示例1
输入
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≤10^{18}\)
题解
思路
知识点:贪心,分治。
显然,每次合并如果两堆糖果数量刚好是合并后总数一半的时候代价最小。
用 \(map\) 记忆化搜索,注意 \(n=0\) 的情况特判。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
map <ll, ll> mp;
ll dg(ll n) {
if (n <= 1) return 0;
if (mp.count(n)) return mp[n];
if (n & 1) return mp[n] = dg(n >> 1) + dg((n >> 1) + 1) + 1;
else return mp[n] = dg(n >> 1) << 1;
}
bool solve() {
ll n;
cin >> n;
cout << dg(n) << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
最新文章
- CALayer基本介绍与常见属性
- 【maven】pom.xml报错:Cannot detect Web Project version.
- .NET 读取本地文件绑定到GridViewRow
- 【小白的CFD之旅】15 四种境界
- 如何让tableViewCell的分割线从边框顶端开始
- SharePoint更改密码
- ZJOI2016二试+游记
- do put in ruby
- spark stream初探
- ios开发者创建app应用开发授权文件 实战方法:
- 虚继承之单继承的内存布局(VC在编译时会把vfptr放到类的头部,这和Delphi完全一致)
- C++ 中 delete 和 delete[] 的区别
- ORACLE JOB创建
- 【转】异步编程 In .NET
- VS2013配置OPENCV2.4.9
- C# .aspx 页面更换命名空间
- Makefile依赖关系中的竖线“|”
- win10 将本地项目上传到github (第一次+再次上传)
- bootstrap-table设置表头宽度无效的解决方案
- 【centos】centos中添加一个新用户,并授权
热门文章
- python黑帽子(第三章)
- linux脚本执行jar包运行
- Oracle 定时任务增删改查
- 关于IPC和PTH用户权限问题,psexec拒绝访问(Access Denied)的原因
- 【翻译】ScyllaDB数据建模的最佳实践
- JZ008和大于等于target的最短数组
- Resource wordnet not found. Please use the NLTK Downloader to obtain the resource:
- 思索 p5.js 的最佳实践
- 基于SqlSugar的开发框架循序渐进介绍(2)-- 基于中间表的查询处理
- [java并发编程]基于信号量semaphore实现限流器