题解 | #可爱の星空#

Description

有 $n$ 个大小为 $1$ 的连通块，规定合并连通块的代价为连通块的大小之差，求将这 $n$ 个联通块合并为 $1$ 个连通块所需的最小代价。

Solution

思路:

显然，当连通块大小相等时合并连通块的代价为 0。
所以我们可以通过分治的思路去解决合并大小为 (n/2) 和 (n - n/2) 最小代价。
对于每个大小为 k 的连通块，只有当 k 为奇数时才有可能产生贡献
当 k 为奇数时，产生的贡献为合并 (k/2 + 1) 的代价 + 合并 (k / 2)的代价 + 1[(k / 2 + 1) - (k / 2)]

所以我们可以通过递归解决这个问题，递归边界是 k == 1。

Tips: 注意到递归函数会多次询问，有可能导致超时，使用 map 记录合并大小为 k 的连通块的最小代价剪枝。

code:

#include <bits/stdc++.h>
#define int long long int
#define endl '\n'
#define pb push_back
using namespace std;

const int N = 1E6 + 70,mod = 1e9 + 7;

map<int,int> mp;

inline int read(){
    char ch = getchar();
    int x =0,f =1;
    for(;!isdigit(ch);ch =  getchar())
        if(ch == '-') f = -1;
    for(; isdigit(ch);ch = getchar())
        x = (x << 1) + (x << 3) + ch - '0';
    return f * x;
}

int get(int x){
    if(mp[x]) return mp[x];
    if(x == 1) return 0;
    return mp[x] = (get(x /2 + (x & 1)) + get(x /2)  + (x & 1));
}

void slove(){
    int n = read();
    cout << get(n) << endl;
}

signed main(){
    int T = 1;
    T = read();
    while(T --){
        slove();
    }
    return 0;
}