ARC124D Yet Another Sorting Problem

tony102

2021 年 11 月 12 日

1829 次浏览

暂无评论

718字数

题解

[Link](https://atcoder.jp/contests/arc124/tasks/arc124_d)

## Sol

联考以来考了好几道这种排列给一个类似于交换排序、冒泡排序的操作，问最小使其有序的操作次数或者方案了。

这道题联考考了一个加强版，要求输出方案（恶心死了）

把每一个 $i \to p_i$ 连边，发现连出来的图长这样：要么是一个自环，要么是一个简单环。这个图里面可能有多个环。

把 $i \leq n$ 的全部标记成黑色，$n < i \leq m$ 的标记成白色，那么只有异色环可以自己每次把 $i$ 和 $p_j = i$ 的位置连回去的操作在环长 $-1$ 次操作消掉自己变成若干个自环。如果是纯色环，那么我们只有把两个不同色的纯色环连在一起变成一个异色环再消掉。

记 $cnt$ 为环的个数，$A$ 为黑色环的个数，$B$ 为白色环个数，那么答案就是  $n + m - cnt + \max (A,B)$

## Idea

1. 排列要排回去的题目考虑 $i \to p_i$ 连边

## Code

```cpp
#include <bits/stdc++.h>
using namespace std;

const int SIZE = 2e5 + 5;

int n, m;
int p[SIZE]; bool cir[SIZE], tag[SIZE];

namespace GTR {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (c < 48 || c > 57) b ^= c == '-', c = fetch();
		while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
		return b ? a : -a;
	}
} using GTR::read;

int main() {
    n = read(), m = read();
    for (int i = 1; i <= n + m; ++ i) p[i] = read(), tag[i] = (i > n);
    int cnt = 0, A = 0, B = 0;
    for (int i = 1; i <= n + m; ++ i) {
        if (cir[i]) continue;
        ++ cnt;
        if (i == p[i]) { cir[i] = 1; continue; }
        int f1 = 1, f2 = 1;
        while (!cir[i]) cir[i] = 1, f1 &= (tag[i] == 0), f2 &= (tag[i] == 1), i = p[i];
        if (f1 && !f2) ++ A;
        if (!f1 && f2) ++ B;
    }
    printf("%d\n", n + m - cnt + 2 * max(A, B));
    return 0;
}
```

最后修改：2021 年 11 月 12 日