题意

• 多组数据
• 每组数据给出一个图中点的个数n，链接任意一条边需要的代价是这个边所连的两个联通块的大小的差值，使这n个点联通所需的最小代价是多少

思路

• 贪心的思考，想让价值最小，每一步合并的两个块得大小接近
• 最终都会合成一个联通图，逆序思考
• 
• 
• 深搜即可

代码

#include<bits/stdc++.h>

using namespace std;
/**
 * 1 0
 * 2 0
 * 3 1
 * 4 0
 * 5 2
 * 6 2
 * 7 2
 * 8 0 100
 * 9 2 101
 * 10 4 110
 * 11 4
 * 12 4
 */


long long dfs(long long n){
    if(n<=2) return 0;
    else if(n==3) return 1;
    else if(n&1) return dfs(n/2)+dfs(n/2+1)+1;
    else return dfs(n/2)*2;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        long long n;
        cin >> n;
        cout << dfs(n) << '\n';
    }
    return 0;
}