题解：CF2041J Bottle Arrangement

喵仔牛奶 · 2025-03-10 12:37:09 · 题解

Solution

本篇题解参考了 Gold14526 的题解，但是将他的做法优化到了除排序外线性，并且代码十分简短。

将 b 从小到大排序。求出整个序列最靠左的最小值的位置 p，考虑 b_n 放在哪里：

• 如果放在 p：剩下的怎么放都合法，若 b_n=a_p 需要操作一次。
• 如果放在 [1,p)：[p,n] 单调递增，直接将最小的几个数 b_1,b_2,\cdots,b_{n-p+1} 放在 [p,n] 里面。若 b_{n-p+1}=a_p 需要操作一次。
• 如果放在 (p,n]：[1,p] 单调递减，直接将最小的几个数 b_1,b_2,\cdots,b_{p} 放在 [1,p] 里面。若 b_{p}=a_p 需要操作一次。

正确性证明：考虑证明放在 [1,p) 时的正确性。如果放的不是这些数，设放在 p 处的是 x，若 x<a_p，由于对于 [1,p) 而言，<a_p 的数是一样的，并不能使答案更小；若 x=a_p，则已经增加了 1 的代价，b_{n-p+1} 在 [1,p) 中最多比原来减少 1 的代价，且不会使不合法的情况变得合法，也不能使答案更小。

发现这样变为了 a,b 规模都缩小的子问题，枚举三种情况，后两种递归解决即可。可以发现递归解决实际上是在遍历笛卡尔树，建立笛卡尔树即可快速处理。复杂度除排序外线性。

Code

#include <bits/stdc++.h>
#define REP(i, l, r) for (int i = (l); i <= (r); ++ i)
using namespace std;
const int N = 1e6 + 5;
int n, tp, a[N], b[N], ls[N], rs[N], s[N];
int slv(int p, int L, int R) { // a 序列还剩下 [L,R]，p 是 [L,R] 的最小值
    if (L > R) return 0;
    int w = 1e9, t1 = n - (p - L), t2 = n - (R - p);
    if (b[t1] <= a[p]) w = min(w, slv(ls[p], L, p - 1) + (b[t1] == a[p]));
    if (b[t2] <= a[p]) w = min(w, slv(rs[p], p + 1, R) + (b[t2] == a[p]));
    return w; // b[n] 放在 p 只有 l=r 才会进行，不需要特判
}
int main() {
    cin >> n;
    REP(i, 1, n) cin >> a[i];
    REP(i, 1, n) cin >> b[i];
    REP(i, 1, n) {
        int x = 0;
        while (tp && a[s[tp]] > a[i]) x = s[tp --];
        if (tp) rs[s[tp]] = i;
        ls[i] = x, s[++ tp] = i;
    }
    sort(b + 1, b + 1 + n);
    int w = slv(s[1], 1, n); 
    cout << (w < 1e9 ? w : -1) << '\n';
    return 0;
}