题意：$ n $ 个人排队, 为他们构造一组身高, 使得 $ x $ 的前面有 $ a_i $ 个人比他高。如果无法构造满足所有条件的身高序列, 输出
-1。
思路：首先考虑, 对于 $ a_i $ 较大的人, 肯定尽可能地将其往队伍后面放, 然后从后往前构造, 因为只有 $ n $ 个人, 因此, 只需要用 $ 1 \sim n $ 去尝试构造一个身高序列即可。对于队列中的某一个人 $ x $, 前面有 $ a_x $ 个比他高的人, 因此要把 $ n - a_i + 1 \sim n $ 留下来构造他前面且比他高的人的身高。接下来考虑无解情况：对于处于位置 $ i $ 的人, 如果 $ a_i > i - 1 $, 则无解。
点击查看代码
#include <bits/stdc++.h>
using i64 = long long;
void solve() {
int n;
std::cin >> n;
std::vector<std::pair<int, std::string>> a;
for (int i = 0; i < n; i++) {
std::string s;
int x;
std::cin >> s >> x;
a.emplace_back(x, s);
}
std::sort(a.begin(), a.end());
std::vector<int> ans(n);
std::vector<bool> vis(n);
for (int i = n - 1; i >= 0; i--) {
if (a[i].first > i) {
std::cout << "-1\n";
return ;
}
for (int j = n - a[i].first; j >= 1; j--) {
if (!vis[j]) {
vis[j] = true;
ans[i] = j;
break;
}
}
}
for (int i = 0; i < n; i++) {
std::cout << a[i].second << " " << ans[i] << "\n";
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0); std::cout.tie(0);
int t = 1;
while (t--) {
solve();
}
return 0;
}