CF1857C Assembly via Minimums 题解

题目

有一个长度为 $n$ 的 $a$ 数组。

给定一个长度为 $\frac{n(n-1)}{2}$ 的 b 数组，由 $\min (a_i,a_j)(1\le i<j\le n)$ 组成。

给定 $b$ 数组，还原出一组可能的 $a$ 数组。

思路

我的思路貌似是全网最独特的？

首先 $a$ 数组的顺序无关紧要，这很显然，因为 min 具有交换律。

其次我们可以发现一个很有用的性质：如果 $a$ 数组中的所有元素都不同，那么若有一个数字 $x$ 在 $b$ 中出现了 $c$ 次，则 $a$ 数组中比 $x$ 大的数就有 $c$ 个。

这也有点显然，因为 $\min (a,b)=a$ 的条件之一就是 $a<b$。那么 $x$ 既然出现了 $c$ 次，那就说明有 $c$ 个数比他大。

知道了这个性质，我们对着样例研究一番就会发现原数组总有一个数会消失，也就意味着有 0 个数比他大，也就是最大的数会在 $b$ 数组中消失。我们补的时候补大于等于数列中的任意一个数就行了。

千万不能补数列中最大的数 + 1，因为题目要求生成的所有数必须小于等于 $10^9$，如果 $b$ 数组中最大的数是 $10^9$ 就直接炸 spj 了，亲身经历，WA on 7。

但是如果 $a$ 中的元素允许相同，处理起来就稍稍有些麻烦，因为自己和自己还能产生贡献。

这时候我们就要想着从大往小去填，这样才能唯一确定相同的数需要填几个。每次填数的时候就看已经填的数，也就是大于等于自己的数的个数，是否等于当前数的出现次数，如果等于就说明这个数只在 $a$ 出现过一次。否则就一直填这个数直到这个数的出现次数与比自己大的数的个数相同为止。

值域有点大，需要离散。这里我用了 map 维护。

代码

//
//  main.cpp
//  C
//
//  Created by SkyWave Sun on 2023/8/7.
//

#include <iostream>
#include <climits>
#include <bitset>
#include <vector>
#include <set>
#include <map>
using namespace std;
#define N ((int)1e3 + 1)
int a[(int)N * (int)N];
void solve() {
    map<int, int> mp;
    int n;
    scanf("%d", &n);
    int maxx = INT_MIN;
    for (int i = 1; i <= (n * (n - 1)) >> 1; ++i) {
        scanf("%d", &a[i]);
        maxx = max(maxx, a[i]);
        ++mp[a[i]];
    }
    vector<int> ans;
    ans.push_back(maxx);
    for (auto pos = --mp.end(); ; --pos) {
        auto i = *pos;
        int num = i.first;
        int cnt = i.second;
        int sz = (int)ans.size();
        ans.push_back(num);
        while (cnt != sz) {
            cnt -= sz;
            ++sz;
            ans.push_back(num);
        }
        if (pos == mp.begin()) {
            break;
        }
    }
    for (auto i : ans) {
        printf("%d ", i);
    }
    putchar('\n');
}
int main(int argc, const char * argv[]) {
//    freopen("in", "r", stdin);
    int T;
    scanf("%d", &T);
    while (T--) {
        solve();
    }
    return 0;
}