Olya and Game with Arrays

Hisaishi_Kanade · 2023-08-14 13:41:06 · 题解

发现全局最小值必然作为某个组的最小值。我们设这个组是 i，那么对于 j\not = i 我们将它的最小值放入 i，使其取得次小值即可构造。

显然的会有一组不能取到次小值，贪心的将全局最小值放入次小值最小的那一组，然后将其他组的最小值也放入这组。

不难发现这就是最优的。

场上拼速度写了一个糟糕的实现。读入每一组对其排序，然后取出第二个值，再排序，将最小的次小值改成全局最小值即可。

#include <bits/stdc++.h>
#define rep(i, l, r) for(i=l; i<=r; ++i)
#define req(i, r, l) for(i=r; i>=l; --i)
using namespace std;
int t, n, i, x, j; long long ret;
const int N=1e5+5;
int a[N], b[N];
int main()
{
    scanf("%d", &t);
    while(t--)
    {
        int mn=1<<30;
        ret=0; scanf("%d", &n);
        rep(i, 1, n)
        {
            scanf("%d", &x);
            rep(j, 1, x)
                scanf("%d", a+j), mn=min(a[j], mn);
            sort(a+1, a+x+1);
            b[i]=a[2];
        }
        sort(b+1, b+n+1);
        b[1]=mn; rep(i, 1, n) ret+=b[i];
        printf("%lld\n", ret);
    }
    return 0;
}