链接:https://ac.nowcoder.com/acm/contest/940/A
来源:牛客网
题目描述
kotori共有n块糖果,每块糖果的初始状态是分散的,她想把这些糖果聚在一堆。但她每次只能把两堆糖果合并成一堆。
已知把两堆数量为a和b的糖果聚在一堆的代价是|a-b|。
kotori想知道,她把这n块糖果聚在一堆的最小代价是多少?
输入描述:
第一行是一个正整数T,代表数据组数。
第二行到第T+1行,每行一个非负整数n,代表kotori的糖果总数量。
输出描述:
每行一个整数,代表kotori需要花费的最小代价。
思路
将一个堆二分,递归求该堆合并的最小代价,用map判重。
代码
#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define LL long long
#define FI first
#define SE second
#define POP pop_back()
#define PII pair<LL,LL>
#define PCC pair<char,char>
#define endl '\n'
#define ls x<<1
#define rs x<<1|1
#define m(x) a[x].l+a[x].r>>1
const int N=1e6+7;
const int INF=1e8,mod=109;
map<LL,LL>mp;
LL f(LL x){
if(mp[x])return mp[x];//如果已经记录
if(x<=1)return mp[x]=0;//小于等于1
if(x&1){
return mp[x]=f(x>>1)+f((x>>1)+1)+1;
}
else{
return mp[x]=f(x>>1)*2;
}
}
int main()
{
int t;
cin>>t;
while(t--){
LL x;
scanf("%lld",&x);
printf("%lld\n",f(x));
}
return 0;
}