自动搬运

查看原文

来自洛谷，原作者为

	K8He あぁ！ 夏を今もう一回

搬运于2025-08-24 23:05:17，当前版本为作者最后更新于2024-09-26 17:08:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这里是 checker 题解。

赛后 UPD：虽然树状数组本来就是要放过去的但是你们怎么都写这个，急眼了。

首先我们知道只有一操作答案是逆序对数。

考虑二操作，注意到存在一种方案是将前 $n - 1$ 个数都删了，所以答案不会超过 $n - 1$，进一步得知最优方案交换次数不超过 $n - 1$。

尝试利用这个上界做一些暴力。直接进行二操作的话，每次操作后序列的交换次数不增，没有什么好的性质。不过如果倒过来进行二操作，依次加当前还没有加的最大值（加入后是序列的最小值），每次操作后序列的交换次数是不降的，然后如果直接暴力插入排序求解，可以在交换次数超过 $n - 1$ 后直接跳出，因为之后一定是更劣解。当然交换次数超过答案就跳了也对因为答案肯定不大于 $n - 1$。

时间复杂度是 $O(n)$，因为插入排序交换操作只会进行 $O(n)$ 次。

#include <bits/stdc++.h>
#define _for(i, a, b) for (int i = a; i <= b; ++i)
#define for_(i, a, b) for (int i = a; i >= b; --i)
#define far(i, vec) for (auto i : vec)
#define bdmd int mid = (l + r) >> 1
typedef long double ldb;
typedef long long ll;
typedef double db;
typedef std::pair <int, int> pii;
typedef std::pair <ll, ll> pll;
const int N = 1e5 + 10, P = 998244353;
namespace IO {
	int rnt () {
		int x = 0, w = 1; char c = getchar ();
		while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
		while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
		return x * w;
	}
}
namespace SOLVE {
	using namespace IO;
	int n, a[N], p[N], b[N], ans;
	void In () {
		n = rnt ();
		_for (i, 1, n) p[a[i] = rnt ()] = i;
		return;
	}
	void Solve () {
		ans = n;
		int S = 0, m = 0;
		for_ (i, n, 1) {
			b[++m] = p[i];
			for_ (j, m, 2) {
				if (b[j] < b[j - 1])
					break;
				std::swap (b[j], b[j - 1]);
				++S;
			}
			if (S > n) break;
			ans = std::min (ans, S + i - 1);
		}
		return;
	}
	void Out () {
		printf ("%d\n", ans);
		return;
	}
}
int main () {
#ifndef ONLINE_JUDGE
	freopen ("data.in", "r", stdin);
	// freopen ("data.out", "w", stdout);
#endif
	SOLVE::In ();
	SOLVE::Solve ();
	SOLVE::Out ();
	return 0;
} /*

*/