本文共 1148 字，大约阅读时间需要 3 分钟。

题目链接：

题目描述

kotori共有n块糖果，每块糖果的初始状态是分散的，她想把这些糖果聚在一堆。但她每次只能把两堆糖果合并成一堆。

输入描述

第一行是一个正整数T，代表数据组数。

输出描述

每行一个整数，代表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 
   
    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;}
   

转载地址：https://lzyws739307453.blog.csdn.net/article/details/94547547 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！