divide-and-conquer

本文最后更新于 2024年7月25日 上午

分治

将大问题转化为等价小问题进行求解。

【分治】随机排列

https://www.acwing.com/problem/content/5469/

题意:给定一个 n 个数的全排列序列,并将其进行一定的对换,问是对换了 3n 次还是 7n+1 次

思路:可以发现对于两种情况,就对应对换次数的奇偶性。当 n 为奇数:3n 为奇数,7n+1 为偶数;当 n 为偶数:3n 为偶数,7n+1 为奇数。故我们只需要判断序列的逆序数即可。为了求解逆序数,我们可以采用归并排序的 combine 过程进行统计即可

时间复杂度:O(nlogn)O(n \log n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1000010;

int n, a[N], t[N];
int cnt; // 逆序数

void MergeSort(int l, int r) {
if (l >= r) return;

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

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

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

while (i <= mid && j <= r) {
if (a[i] < a[j]) t[idx++] = a[i++];
else {
cnt += mid - i + 1;
t[idx++] = a[j++];
}
}

while (i <= mid) t[idx++] = a[i++];
while (j <= r) t[idx++] = a[j++];

for (i = l, idx = 0; i <= r; i++, idx++) a[i] = t[idx];
}

void solve() {
cin >> n;

for (int i = 0; i < n; i++) cin >> a[i];

MergeSort(0, n - 1);

int res;

if (n % 2 == 1) {
if (cnt % 2) res = 1;
else res = 2;
} else {
if (cnt % 2) res = 2;
else res = 1;
}

cout << res << "\n";
}

signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int T = 1;
// cin >> T;
while (T--) solve();
return 0;
}

divide-and-conquer
https://blog.dwj601.cn/Algorithm/divide-and-conquer/
作者
Mr_Dwj
发布于
2024年3月21日
更新于
2024年7月25日
许可协议