题解：CF2041J Bottle Arrangement

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

CPP

#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;
}

题解：CF2041J Bottle Arrangement

文章操作

Solution

Code

相关推荐

评论

题解：CF2041J Bottle Arrangement