[洛谷P1966] 火柴排队

题目链接：

题目分析：

感觉比较顺理成章地就能推出来？似乎是个一眼题

交换的话多半会往逆序对上面想，然后题目给那个式子就是拿来吓人的根本没有卵用

唯一的用处大概是告诉你考虑贪心一波，很显然有两个序列中每对排名对应的数放在同一位置上是最优策略这个结论

说详细一点，假设\(a_0\)是\(a\)序列中的第\(k\)大，\(b_0\)是\(b\)序列中的第\(k\)大，那么\(a_0\)和\(b_0\)肯定需要交换到同一个位置上，然后相减。

然后我们考虑怎么交换次数最少

先考虑最简单粗暴的交换方法：两个序列分别排个序，这样排名肯定一一对应

这样的话交换次数是两个序列中逆序对数量之和

但是这样并不是最优的，比如说两个序列中的排名可以都是1423。如果我们直接排序，会出现我们本来进行一次交换就能搞定的一对数，为了把他换到排名相符的地方去，又一起往前换了（比如两个序列都已经1423了，但是如果直接排序就会有4和2再进行一下不必要的交换这样的情况），这对答案其实是没有贡献的

然后我们考虑怎样优化

首先发现其实问题和这个数本身没什么关系，主要是和数的排名有关系，所以可以先把数组离散化

然后就是我也不知道自己怎么想到的了……先把第一个序列的每个数优先级重新定义一下

比如说

1 3 4 2

我们把它每个元素的优先级定义成

1 2 3 4

1 3 4 2

（上下对应的）

然后我们用我们自己定义的优先级重新定义第二个序列，假设第二个是

1 4 2 3

然后我们把它替换成

1 3 4 2

这样我们得到新的两个序列是

1 2 3 4

1 3 4 2

保证第一个序列不动，这个时候就交换第二个序列的元素来和第一个的排名匹配上就可以了（因为换第一个和换第二个其实本质上没有差别）

交换次数就是第二个序列里的逆序对数，归并排序或者树状数组

代码：

实现不难，我写的归并，这个代码因为是赶时间写的长得很丑，重点在上面分析

#include <bits/stdc++.h>

#define int long long

#define N (100000 + 20)

using namespace std;

inline int read() {

	int cnt = 0, f = 1; char c = getchar();

	while (!isdigit(c)) {if (c == '-') f = -f; c = getchar();}

	while (isdigit(c)) {cnt = (cnt << 3) + (cnt << 1) + c - '0'; c = getchar();}

	return cnt * f;

}

int n, a[N], b[N << 1], a_[N], res, cnt, ans;

int New[N];

void Discretization(int a[]) {

	sort(b + 1, b + n + 1);

	int q = unique(b + 1, b + n + 1) - b;

	for (register int i = 1; i <= n; i++)

		a[i] = lower_bound(b + 1, b + q + 1, a[i]) - b - 1;

}

int merge(int l, int r) {

	int mid = (l + r) >> 1;

	int i = l, j = mid + 1; cnt = 0;

	for (register int k = l; k <= r; k++)

		if (j > r || (i <= mid && a_[i] < a_[j])) b[k] = a_[i++];

		else b[k] = a_[j++], cnt += (mid - i + 1) % 99999997;

	for (register int k = l; k <= r; k++) a_[k] = b[k];

	return cnt;

}

int solve(int l, int r) {

	if (l < r) {

		int mid = (l + r) >> 1;

		solve(l, mid), solve(mid + 1, r);

		ans += merge(l, r);

	}

	return ans;

}

signed main() {

	n = read();

	for (register int i = 1; i <= n; i++) a[i] = b[i] = read();

	Discretization(a);

	for (register int i = 1; i <= n; i++) a_[i] = b[i] = read();

	Discretization(a_);

	for (register int i = 1; i <= n; i++) New[a[i]] = i;

	for (register int i = 1; i <= n; i++) a_[i] = New[a_[i]];

//	for (register int i = 1; i <= n; i++) cout<<a_[i]<<" ";

//	cout<<endl;

	memset(b, 0, sizeof(b));

	res = solve(1, n) % 99999997;

	printf("%d", res % 99999997);

	return 0;

}

巴特西

[洛谷P1966] 火柴排队

题目链接：

题目分析：

代码：

最新文章

热门文章