欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

『贪心·二分答案』排序

程序员文章站 2022-03-11 23:29:41
...

P r o b l e m \mathrm{Problem} Problem

『贪心·二分答案』排序


S o l u t i o n \mathrm{Solution} Solution

这道题有一个很神奇的性质:交换操作与操作顺序无关

这意味着,我们形如 a b a b a b . . . ababab... ababab... 的操作顺序可以改变成形如 a a a b b b . . . aaabbb... aaabbb... 的顺序。

考虑证明:若有交换操作 ( a , b ) (a,b) (a,b) ( c , d )   ( a < b , c < d ) (c,d)\ (a<b,c<d) (c,d) (a<b,c<d).

  • 自己和自己交换显然满足上述结论,故不作考虑。
  • a , b , c , d a,b,c,d a,b,c,d 四个数不相同,则两个操作可以交换。
  • a = c , b = d a=c,b=d a=c,b=d,则两个交换本生便没有意义,故可以交换。
  • a = d a=d a=d b = c b=c b=c,则两次操作形如 ( a , b ) (a,b) (a,b) ( b , c ) (b,c) (b,c),则该操作可以用 ( b , c ) (b,c) (b,c) ( a , c ) (a,c) (a,c) 代替;若形式为 ( b , c ) (b,c) (b,c) ( a , b ) (a,b) (a,b) ,则可以使用 ( a , b ) (a,b) (a,b) ( a , c ) (a,c) (a,c) ,那么只要其中的某一个是Alice的操作,则Alice和Bob的操作顺序一定可以通过Bob的改变而交换。
  • a = c a=c a=c b = d b=d b=d,则证明方法与上面同理。

操考试就应该大胆猜想的

上述结论说明了: a b ab ab 操作和 b a ba ba 是等下的,那么若干次等价交换我们就可以得到上述交换顺序的改变。显然答案具有单调性,我们尝试枚举Alice的熟悉 x x x

  • 我们交换完Alice的前 x x x 的操作以后,我们我们只判定改变当前数列的次数是否 ≤ x \le x x 即可。因此少了,我们可以用自我交换完成填充。

C o d e \mathrm{Code} Code

#include <bits/stdc++.h>

using namespace std;
const int N = 7e5;

int n, m;
int a[N], vis[N], b[N], x[N], y[N];

int read(void)
{
	int s = 0, w = 0; char c = getchar();
	while (!isdigit(c)) w |= c == '-', c = getchar();
	while (isdigit(c)) s = s*10+c-48, c = getchar();
	return w ? -s : s;
}

void Dfs(int x)
{
	vis[x] = 1;
	if (vis[b[x]] == 0) Dfs(b[x]);
}

bool check(int t)
{
	int res = n;
	for (int i=1;i<=n;++i) {
		b[i] = a[i];
		vis[i] = 0;
	}
	for (int i=1;i<=t;++i) swap(b[x[i]], b[y[i]]);
	for (int i=1;i<=n;++i)
		if (vis[i] == 0) Dfs(i), res --;
	return res <= t;
}

int main(void)
{
	freopen("sort.in","r",stdin);
	freopen("sort.out","w",stdout);
	n = read();
	for (int i=1;i<=n;++i) a[i] = read() + 1;
	m = read();
	for (int i=1;i<=m;++i) {
		x[i] = read() + 1;
		y[i] = read() + 1;
	} 
	int l = 0, r = m;
	while (l + 1 < r) {
		int mid = l + r >> 1;
		if (check(mid)) r = mid;
		else l = mid;
	}
	if (check(l)) cout << l << endl;
	else cout << r << endl;
	return 0;
}