分治
分治法會把問題分解成子問題（分），解決完再合併回原本的問題（治）。分治分成以下步驟
- 切割：把一個問題切成子問題然後遞迴
- 終止條件：停止切割，算出答案回傳。
- 合併：利用傳回來的子問題算出答案然後回傳
合併排序法
- 切割：把序列分成兩半然後遞迴。
- 終止條件：直到序列長度為 1，這時候已為一個排好的序列，直接回傳。
- 合併：利用傳回來的兩序列（左序列、右序列）進行排序。合併的方法為比較兩序列最左邊的元素，較小的元素排在前頭，要特別注意某個序列為空的情況。
實作時需多開一個陣列暫存，開兩個整數 分別維護左右序列目前比較的位置。
合併排序法是穩定的演算法，會遞迴 層，合併的時間複雜度為 ，因此時間複雜度為 。
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 | using namespace std;
const int N = 100;
int arr[N], buf[N];
void sol(int L, int R)
{ // [L,R)
if (R - L <= 1)
return;
int M = (R + L) / 2;
sol(L, M);
sol(M, R);
int i = L, j = M, k = L;
while (i < M || j < R)
{
if (i >= M)
buf[k] = arr[j++];
else if (j >= R)
buf[k] = arr[i++];
else
{
if (arr[i] <= arr[j])
buf[k] = arr[i++];
else
{
buf[k] = arr[j++];
}
}
k++;
}
for (int k = L; k < R; k++)
arr[k] = buf[k];
return;
}
|
逆序數對
逆序數對
給定一個長度為 的序列，求有幾組數對 滿足 且 。
這題我們可以轉換成，給定一個序列 ，在只能將相鄰位置交換的情況下，需要換幾次才能將序列從小排到大。
交換次數可以在合併排序法的「合併」程式碼中計算，只要右序列有元素小於前面的元素，就會形成逆序數對，也就是上面範例程式碼 arr[i]>arr[j] 的情況，這時候每一個左序列尚未排序完畢的元素，都會和 arr[j] 形成逆序數對。
參考程式碼
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 | #include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define L 500010
int arr[L], buf[L];
long long sol(int left, int right)
{
if (right - left <= 1)
return 0;
int middle = (right + left) / 2;
long long ans = sol(left, middle) + sol(middle, right);
int i = left, j = middle, k = left;
while (i < middle || j < right)
{
if (i >= middle)
buf[k] = arr[j++];
else if (j >= right)
buf[k] = arr[i++];
else
{
if (arr[i] <= arr[j])
buf[k] = arr[i++];
else
{
buf[k] = arr[j++];
ans += middle - i;
}
}
k++;
}
for (int k = left; k < right; k++)
arr[k] = buf[k];
return ans;
}
int main()
{
int n;
while (cin >> n, n)
{
memset(arr, 0, sizeof(arr));
memset(buf, 0, sizeof(buf));
for (int i = 0; i < n; i++)
cin >> arr[i];
cout << sol(0, n) << endl;
}
}
|
UVa 10810 - Ultra-QuickSort
給定序列 ，求使用泡沫排序法需要交換的次數，泡沫排序法會從左到右比較相鄰兩數，如果左邊的數較大就交換兩數。
一個數字 會跟所有在 右邊，且小於 的數字交換位置，換句話說，就是和 形成逆序數對的數字，所以這題要求的是逆序數對的數量。
UVa 11495 - Bubbles and Buckets
給定序列 ，兩個輪流交換兩個相鄰數字(左邊數字必須大於右邊才可交換)，讓序列由小到大排序的人獲勝，請問獲勝的是先手還是後手?
同樣求逆序數對的數量，奇數先手勝，偶數後手勝。
快速排序法
- 切割：選定一個基準點 ，將其他數字分成兩堆， 的數字排在 前面， 的數字排放在 的後面，分堆完成，再分別遞迴排序兩堆。
- 終止條件：直到序列長度為 1，這時候已為一個排好的序列，直接回傳。
- 合併：已經排好順序，不需要額外的合併動作。
快速排序法是一種不穩定的演算法，最好時間複雜度為 ，最差時間複雜度為 。
二維平面上最近點對
二維平面上最近點對
給定二維平面上的 個點，要找出距離最近的兩個點。
一開始先將點依 座標排序。
- 切割：將點分成一半，分別遞迴。
- 終止條件：點數 ，用兩層迴圈找出最近點對。
- 合併：
- 設目前最小的點對距離為 。
- 左邊點集 ，右邊點集為 。
- 兩點集的中點為 。
- 設點集
- 首先找出 ，因為要找到比 找的點對會在 裡，接著把 裡的點對 座標排序。接著將每個點和比自己的 座標大的點取距離，如果有 就更新值，如果遇到跟自己的 座標相差超過 的點就停止比較（不可能距離會 )。
合併的算法看似是 ，但實際上只會列舉 個點左右（這方面待證實正確個數，在此只要知道是一個很小的數），時間複雜度為 。
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 | #include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
using namespace std;
using dvt = double;
const dvt INF = 1e20;
const int MXN = 1e5 + 5;
struct dot
{
dvt x, y;
} p[MXN], tmp[MXN];
bool cmpX(dot a, dot b) { return a.x < b.x; }
bool cmpY(dot a, dot b) { return a.y < b.y; }
dvt getDis(dot a, dot b)
{
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
dvt nearestPair(int L, int R)
{
if (L == R)
{
return INF;
}
if (L + 1 == R)
{
return getDis(p[L], p[R]);
}
int M = (L + R) >> 1;
dvt d = min(nearestPair(L, M), nearestPair(M, R));
int k = 0;
for (int i = L; i <= R; ++i)
{
if (fabs(p[i].x - p[M].x) <= d)
{
tmp[k++] = p[i];
}
}
sort(tmp, tmp + k, cmpY);
for (int i = 0; i < k; ++i)
{
for (int j = i + 1; j < k && tmp[j].y - tmp[i].y < d; ++j)
{
double d2 = getDis(tmp[i], tmp[j]);
d = min(d, d2);
}
}
return d;
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i)
{
scanf("%lf%lf", &p[i].x, &p[i].y);
}
sort(p, p + n, cmpX);
dvt res = nearestPair(0, n - 1);
printf("%.2lf\n", res);
}
|
相關題目
UVA 1608：Non-boring sequences
給定一個序列 ，判斷使否每一個連續的子序列，都有一個數字，只在該子序列出現一次。
只要在序列 中找到一個符合的數字 ，那麼所有在 到 之間，包含 的連續子序列都符合，接著再判斷 和 兩個子序列是否符合即可。
此外如果 只從一端開始找，最差的時間複雜度為 ，為了避免超時，從兩端開始找，最差的情況就是每次都剛好在中間找到 ，時間複雜度為 。
參考程式碼
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 | #include <iostream>
#include <map>
using namespace std;
const int N = 200005;
int a[N], L[N], R[N];
bool sol(int a, int b)
{
if (a >= b)
return 1;
for (int i = 0; i <= (b - a) / 2; i++)
{
if (L[a + i] < a && b < R[a + i])
{
return sol(a, a + i - 1) && sol(a + i + 1, b);
}
if (L[b - i] < a && b < R[b - i])
{
return sol(a, b - i - 1) && sol(b - i + 1, b);
}
}
return 0;
}
int main()
{
int t, n;
map<int, int> tb;
cin >> t;
while (t--)
{
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
tb.clear();
for (int i = 0; i < n; i++)
{
if (tb.find(a[i]) == tb.end())
{
L[i] = -1;
}
else
{
L[i] = tb[a[i]];
}
tb[a[i]] = i;
}
tb.clear();
for (int i = n - 1; i >= 0; i--)
{
if (tb.find(a[i]) == tb.end())
{
R[i] = n;
}
else
{
R[i] = tb[a[i]];
}
tb[a[i]] = i;
}
cout << (sol(0, n - 1) ? "non-boring\n" : "boring\n");
}
}
|
Codefocdes 1490D - Permutation Transformation
給定一組 permutation ，要將這個排列轉成一顆二元樹，作法為：
- 將最大的數字當成根，該數字左右兩邊的數列，分別當成左右子樹。
- 子樹依相同方式建構。
請問在轉化成二元樹後，每一個數字的深度為何?
大小最多為 ，用遞迴解的時間複雜度 不會超過時限的。搜尋一個區間 ，找到最大的數字 ，更新他的深度，繼續遞迴 和 。
例題練習