我一年前甚至不会做/qd
发现 \(a_{x_1}\) 为 \(k = \min\limits_{i=1}^n a_i\) 时最优。然后开始分类讨论:
- 如果 \(\min\limits_{a_i = k} a_{i+n} \le k\),答案为 \((k, \min\limits_{a_i = k} a_{i+n})\)。这是因为如果再选一个 \(k\) 肯定不优。
- 否则我们肯定尽可能先把 \(k\) 选完。接下来讨论最后一个 \(k\) 的位置直到 \(n\) 还能不能再选。设 \(p\) 为第一个 \(a_p = k\) 的位置。
- 每次选的数要保证 \(\le a_{p+n}\) 且是当前区间内的最小值,不然不优。
- 当当前区间内最小值 \(= a_{p+n}\) 时有些特殊。如果 \(a_{p+n}\) 大于它后面被选的第一个 \(\ne a_{p+n}\) 的数,或者它后面不存在 \(\ne a_{p+n}\) 的数,那么选了这个区间最小值也不优。
实现时使用 ST 表查询区间最小值,复杂度 \(O(n \log n)\)。
code
// Problem: D - Concatenate Subsequences
// Contest: AtCoder - AtCoder Regular Contest 134
// URL: https://atcoder.jp/contests/arc134/tasks/arc134_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;
const int maxn = 200100;
const int logn = 20;
const int inf = 0x3f3f3f3f;
int n, a[maxn], lg[maxn];
pii f[maxn][logn];
inline pii qmin(int l, int r) {
int k = lg[r - l + 1];
return min(f[l][k], f[r - (1 << k) + 1][k]);
}
void solve() {
scanf("%d", &n);
for (int i = 2; i <= n * 2; ++i) {
lg[i] = lg[i >> 1] + 1;
}
for (int i = 1; i <= n * 2; ++i) {
scanf("%d", &a[i]);
if (i <= n) {
f[i][0] = make_pair(a[i], i);
}
}
for (int j = 1; (1 << j) <= n; ++j) {
for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
}
int mn = *min_element(a + 1, a + n + 1), pos = -1, t = inf;
for (int i = 1; i <= n; ++i) {
if (a[i] == mn) {
t = min(t, a[i + n]);
}
}
if (t <= mn) {
printf("%d %d\n", mn, t);
return;
}
vector<int> vc, tv;
for (int i = 1; i <= n; ++i) {
if (a[i] == mn) {
vc.pb(i);
pos = i;
tv.pb(a[i + n]);
}
}
int x = -1;
for (int i = 0; i < (int)tv.size(); ++i) {
if (tv[i] != tv[0]) {
x = tv[i];
break;
}
}
while (pos < n) {
pii p = qmin(pos + 1, n);
if (p.fst > tv[0] || (p.fst == tv[0] && tv[0] > x)) {
break;
}
vc.pb(p.scd);
pos = p.scd;
}
for (int x : vc) {
printf("%d ", a[x]);
}
for (int x : vc) {
printf("%d ", a[x + n]);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- Subsequences Concatenate AtCoder Regular Contestsubsequences concatenate atcoder regular atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest 166 atcoder regular contest degree atcoder regular contest 167 atcoder regular contest sliding atcoder regular contest 164 atcoder regular contest builder disconnected atcoder regular contest