CF2133B Villagers题解

· · 题解

CF2133B Villagers题解

题意

一个村庄里有 n 个村民，每个村民有一个脾气值 g_i。
刚开始，村庄里的每一个村民都不是朋友。
Steve 可以选择两个村民 i 和 j，花费 \max (g_i, g_j) 个绿宝石让他们成为朋友，并且他们的脾气值会减少 \min (g_i, g_j)。
Steve 想要让村庄里的每一个人都成为朋友（可能有一些中间朋友）。
但是 Steve 不想让村庄经济膨胀太多，所以他想知道最少的绿宝石花费是多少。

形式化题意

有一个 n 个节点的无向图，刚开始有 0 条边。
每次连接 u 和 v 节点需要的代价是 \max (g_u, g_v)，之后 g_u 和 g_v 都会减少 \min (g_u, g_v)。
求将此图变为连通图的最小代价。

分析

考虑贪心。每次建边的花费是 \max (g_i, g_j)，那每次连接的两个点一定是当前未被连接过的点权最大、次大节点。否则花费就会多出 g_{\text{当前点权次大节点}} - g_{\text{当前点权第} 3 \text{大节点}}。
这样处理过后，图中会有 \lfloor \frac {n}{2} \rfloor 个连通子图。对于每两个大小为 2 连通子图，连接它们的代价为 0。因为在连接任意大小为 2 的连通子图时，其中较小 g 值变为 0。此时连接它们的最优策略是连接两个 g 值为 0 的节点，此时代价为 0。如果此时 n 为偶数，那么已经完成。如果 n 为奇数，此时还剩余一个 g 值最小的大小为 1 的连通子图，只需要将它与任意一个 g 值为 0 的节点连接即可。

代码部分

#include <bits/stdc++.h>
using namespace std;
int T;
void solve(){
    int n;
    cin >> n;
    vector <int> a(n + 1);
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a.begin() + 1, a.end());//STL内置排序
    long long ans = 0;
    for(int i = n; i > 0; i -= 2)//这里条件不能写 i，因为当 n 为奇数时，会出现 i = -1 的情况
        ans += a[i];//连接部分
    cout << ans << endl;
}
int main(){
    cin >> T;
    while(T--){
        solve();
    }
    return 0;
}