题目链接：https://ac.nowcoder.com/acm/contest/940/A/
时间限制：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:

#include <bits/stdc++.h>
using 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;
}