P7726 天体探测仪（Astral Detector）

题目背景

通过远古档案馆的探索，你成功制出了天体探测仪，你需要用它发现潜藏的天体科技。

题目描述

想要找到天体科技，你需要先得到一串天体密码——它是一个 $1 \sim n$ 的排列。

天体探测仪允许对于给定的长度 $l$，返回密码中一个长度为 $l$ 的区间的最小值。

不幸的是，所有长度为 $l$ 的区间最小值混在了一起，你得到的只是 $n$ 个可重集合 $S_1, \ldots , S_n$：

• $S_i$ 表示所有长度为 $i$ 的区间最小值构成的可重集合。

你需要根据这些 $S_i$，还原出一种可能的天体密码，保证至少存在一种正确的天体密码。

输入格式

第一行，一个整数 $n$，表示天体密码的长度。

接下来 $n$ 行，其中第 $i$ 行包含 $n - i + 1$ 个整数（长度为 $i$ 的区间共有 $n - i + 1$ 个），表示可重集 $S_i$ 中的每个元素，注意元素的顺序是任意的，而不一定是按照区间从左到右的顺序。

输出格式

输出一行 $n$ 个整数 $p_1, p_2, \ldots , p_n$，表示你还原出的天体密码。

如有多种可行解，可以输出任意一种。

输入输出样例 #1

输入 #1

4
4 3 2 1
1 2 1
1 1
1

输出 #1

3 1 2 4

说明/提示

【样例 1 解释】

样例输出的天体密码为：$p = [3, 1, 2, 4]$。

长度为 $1$ 的区间最小值构成的可重集合：$S_1 = \{ 3, 1, 2, 4 \} = \{ 4, 3, 2, 1 \}$。

长度为 $2$ 的区间最小值构成的可重集合：$S_2 = \{ \min(3, 1), \min(1, 2), \min(2, 4) \} = \{ 1, 1, 2 \} = \{ 1, 2, 1 \}$。

长度为 $3$ 的区间最小值构成的可重集合：$S_3 = \{ \min(3, 1, 2), \min(1, 2, 4) \} = \{ 1, 1 \}$。

长度为 $4$ 的区间最小值构成的可重集合：$S_4 = \{ \min(3, 1, 2, 4) \} = \{ 1 \}$。

每一个 $S_i$ 都与输入对应。

其他可行答案也判为正确，如 $p = [4, 2, 1, 3]$。

---

【数据范围】

本题采用捆绑测试。

对于 $100\%$ 的数据：$2 \le n \le 800$。

子任务编号	分值	$n \le$	特殊限制
$1$	$26$	$6$	无
$2$	$24$	$16$
$3$	$12$	$800$	对于每个 $i \in [1, n]$，$S_i$ 中不存在两个相同元素
$4$	$38$		无

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int n;
int cnt[805][805];
int mx_len[805];
int ans[805];

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i=1; i<=n; ++i){
        for(int j=0; j<n-i+1; ++j){
            int val; cin >> val;
            cnt[val][i]++;
            mx_len[val] = max(mx_len[val], i);
        }
    }

    multiset<pair<int,int>> holes;
    holes.insert({n, 1});

    for(int v=1; v<=n; ++v){
        int len = mx_len[v];
        auto it = holes.lower_bound({len, -1});
        int size = it->first;
        int start = it->second;
        holes.erase(it);

        int pos = 0;
        for(int k=1; k<=size; ++k) pos = max(pos, cnt[v][k]);
        
        ans[start + pos - 1] = v;
        
        if(pos > 1) holes.insert({pos - 1, start});
        if(size - pos > 0) holes.insert({size - pos, start + pos});
    }

    for(int i=1; i<=n; ++i) cout << ans[i] << (i==n ? "" : " ");
    cout << "\n";
    return 0;
}