abcdeffa's Blog

当局者迷，旁观者清。

0%

GMOJ S3776 【序列排序】

发表于 更新于

Description

给你一个正整数 $n$ 和一个正整数序列 $a_1$ ~ $a_n$ ，你可以任意交换 $a_i$ 和 $a_j(1 \leq i, j \leq n)$ ，代价为 $(a_i + a_j)$ ，求将原序列按升序排序所需的最小代价。

Solution

我们可以先通过排序求出每个数要去到的位置，然后从原位置到目标位置连边。

我们发现这样的图会是由多个环组成的（包括自环）。

考虑只有一个环，那么如果我们设 $mi$ 表示环内的数的最小值， $su$ 表示环内的所有数的和， $size$ 为环内的数的个数，那么我们不难得出答案为 $[su + mi(size - 2)]$ 。

当有多个环时，我们可以考虑把全局最小值与环内最小值交换，然后将环内的数排好以后，再把全局最小值与原先的环内最小值换回来，或者不交换全局最小值与环内最小值。

所以，如果我们设全局最小值为 $Mi$ ，那么答案为：

。

于是我们对每个环做一遍 DFS ，然后将代价加起来即可得到答案。

时间复杂度 $O(n)$ 。

Code

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <cstdio>
#define maxN 100010
long long color[maxN], cu[maxN], a[maxN][2], b[maxN];
long long ans = 0, Mi = 2147483647;
long long min (long long x, long long y)
{
	return x < y ? x : y;
}
void px (long long l, long long r)
{
	long long x = l, y = r, mid = a[(l + r) / 2][0];
	while(x <= y)
	{
		while(a[x][0] < mid)
		{
			x++;
		}
		while(a[y][0] > mid)
		{
			y--;
		}
		if(x <= y)
		{
			long long t = a[x][0];
			a[x][0] = a[y][0];
			a[y][0] = t;
			t = a[x][1];
			a[x][1] = a[y][1];
			a[y][1] = t;
			x++;
			y--;
		}
	}
	if(l < y)
	{
		px(l, y);
	}
	if(x < r)
	{
		px(x, r);
	}
}
void dfs (long long st, long long x, long long mi, long long su, long long flag, long long size)
{
	color[x] = 1;
	if(st == x && flag)
	{
		ans += (su - mi) + min(Mi * (size - 1) + 2 * (mi + Mi), (size - 1) * mi);
		return ;
	}
	dfs(st, cu[x], min(mi, b[x]), su + b[x], 1, size + 1);
}
int main ()
{
	long long n = 0;
	scanf("%lld", &n);
	for(long long i = 1;i <= n; i++)
	{
		scanf("%lld", &a[i][0]);
		Mi = min(Mi, a[i][0]);
		b[i] = a[i][0];
		a[i][1] = i;
	}
	px(1, n);
	for(long long i = 1;i <= n; i++)
	{
		cu[a[i][1]] = i;
	}
	for(long long i = 1;i <= n; i++)
	{
		if(a[i][1] == i)
		{
			continue;
		}
		if(!color[i])
		{
			dfs(a[i][1], a[i][1], 2147483647, 0, 0, 0);
		}
	}
	printf("%lld", ans);
	return 0;
}