专栏文章

CF2133B Villagers题解

SS1lver_W0lf
CF2133B题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio5k1n8
此快照首次捕获于
2025/12/02 13:43
3 个月前
此快照最后确认于
2025/12/02 13:43
3 个月前
查看原文

CF2133B Villagers题解

题意

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

形式化题意

有一个 nn 个节点的无向图，刚开始有 00 条边。
每次连接 uu 和 vv 节点需要的代价是 max⁡(gu,gv)\max (g_u, g_v)，之后 gug_u 和 gvg_v 都会减少 min⁡(gu,gv)\min (g_u, g_v)。
求将此图变为连通图的最小代价。

分析

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

代码部分

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...