题目链接:https://www.luogu.com.cn/problem/P11839
思路
由于我们看到了题目要求字典序最大,那么就是要求选的尽量大,宁愿抛弃一些,也要保证前面尽可能的大。
那么,我们可以想到把输入的数组按值从大到小为第一关键字,在原数组的位置从小到大为第二关键字,因为尽量靠前可以使得后面能接更多的数。
我们按照排序后的数组遍历,并且记录已经记录的最靠后的和第二靠后的。为了使得答案最有,我们唯一一次可以操作的机会应当留给前面被比这个数小的数阻挡的数。
由于我们想要字典序最大,所以前面的应当尽可能的最大,所以我们把这一次机会给遍历中的第一个需要这个机会的。
我们可以发现,如果按数值从大到小遍历中有一个数的位置 $x$ 满足 $max1 > x > max2$,这样就可以把 $max1$ 提前到 $x$ 前面,这样 $max1$ 和 $x$ 都能用了。
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, a[1000005], b[1000005], maxn[1000005];
struct node {
int id, v;
} c[1000005];
bool cmp(node x, node y) {
if (x.v != y.v) return x.v > y.v;
else return x.id < y.id;
}
void solve() {
cin >> n;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
b[i] = a[i];
c[i].v = a[i];
c[i].id = i;
}
sort(b + 1, b + n + 1);
sort(c + 1, c + n + 1, cmp);
int maxn, ma2, moved = 0;
maxn = ma2 = 0;
for (int i = 1; i <= n; i ++) {
if (c[i].id > maxn) {
ma2 = maxn;
maxn = c[i].id;
cout << c[i].v << " ";
} else if (c[i].id > ma2 && moved == 0) {
maxn = c[i].id;
moved = 1;
cout << c[i].v << " ";
}
}
cout << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T; cin >> T;
while (T --) {
solve();
}
return 0;
}