高效算法设计

这里主要实现了一些和算法有关的问题
先介绍一下最基本的算法分析模版
然后图解一些思维的技巧

分治算法,快速排序

MergeSort

mergeSort

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
83
84
85
86
87
88
//
// main.cpp
// mergeSort
//
// Created by zhangmin chen on 2019/5/3.
// Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<string>::iterator ssii;

#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;

const int maxn = 100000000;
int A[maxn];
int T[maxn];
int n;
int cnt = 0;

void init() {
// static int cnt = 0;
cnt = 0;
memset(A, 0, sizeof(A));
memset(T, 0, sizeof(T));
}

void mergeSort(int* A, int x, int y, int* T) {
if(y - x > 1) {
int mid = x + (y-x) / 2;
int p = x, q = mid;

int i = x;

mergeSort(A, x, mid, T);
mergeSort(A, mid, y, T);

while(p < mid || q < y) {
if( (q >= y) || (p < mid && A[p] <= A[q]) ) T[i++] = A[p++];
else {
T[i++] = A[q++];
cnt += mid-p;
}
}

for(int i = x; i < y; i++) A[i] = T[i];
}
}

int main() {
freopen("input.txt", "r", stdin);
// static int n;
// init();
cin >> n;
init();

for(int i = 0; i < n; i++) {
cin >> A[i];
}

// mergeSort
mergeSort(A, 0, n, T);
for(int i = 0; i < n; i++) cout << A[i] << " ";
cout << endl;

cout << "cnt: " << cnt << endl;
}

QuickSort

quicksort

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
//
// main.cpp
// quicksort
//
// Created by zhangmin chen on 2019/5/3.
// Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<string>::iterator ssii;

#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;

const int maxn = 1000000;
int n;
int A[maxn];

void init() {
memset(A, 0, sizeof(A));
}

void quicksort(int* A, int lo, int hi) {
if(lo > hi) return;

int pivot = A[lo];

int i = lo, j = hi;

while(i != j) {
while(A[j] >= pivot && i < j) j--;
while(A[i] <= pivot && i < j) i++;

if(i < j) swap(A[i], A[j]);
}

A[lo] = A[i];
A[i] = pivot;

quicksort(A, lo, i-1);
quicksort(A, i+1, hi);
}

int main() {
freopen("input.txt", "r", stdin);
cin >> n;
init();

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

quicksort(A, 0, n-1);
for(int i = 0; i < n; i++) cout << A[i] << " ";
cout << endl;
}

反转子序列:类快排思想

UVA120

UVA120

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
//
// main.cpp
// UVA120
//
// Created by zhangmin chen on 2019/5/19.
// Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<string>::iterator ssii;

const int inf = 0x3f3f3f3f;

#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;

const int maxn = 100;
int A[maxn];
int n;

void init() {
Set(A, 0);
}

void flip(int p) {
for(int i = 0; i < p-i; i++) {
swap(A[i], A[p-i]);
}
printf("%d ", n-p);
}

int main() {
freopen("input.txt", "r", stdin);
string line;
while (getline(cin, line)) {
init();
stringstream ss(line);
n = 0;
while(ss >> A[n]) n++;
_for(i, 0, n) printf("%d ", A[i]);
printf("\n");

for(int i = n-1; i > 0; i--) {
// i is the position of top
// [begin, end) max element
long ith = max_element(A, A+i+1) - A;
if((int)ith == i) continue;

if(ith > 0) flip((int)ith);
flip(i);
}
printf("0\n");
}
}

贪心算法:若干区间选出n个点

UVA11134

UVA11134

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
83
84
85
86
87
88
89
90
//
// main.cpp
// UVA11134
//
// Created by zhangmin chen on 2019/5/19.
// Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<string>::iterator ssii;

const int inf = 0x3f3f3f3f;
const int maxn = 5000 + 5;

#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;

bool inRange(int lo, int hi, int x) {
if(lo > hi) return inRange(hi, lo, x);
return lo <= x && x <= hi;
}

int xl[maxn], xr[maxn], yl[maxn], yr[maxn];
int x[maxn], y[maxn];

void init() {
Set(xl, 0);
Set(xr, 0);
Set(yl, 0);
Set(yr, 0);
Set(x, 0);
Set(y, 0);
}

bool solve(int* l, int* r, int* res, int n) {
fill(res, res+n, -1);

_rep(val, 1, n) {
int p = -1, minr = n+1;
// choose min interval for each val

_for(i, 0, n) {
if(val >= l[i]) {
if(res[i] < 0 && r[i] < minr) { minr = r[i]; p = i; }
}
}
if(val > minr || p < 0) return false;
res[p] = val;
}
return true;
}

int n;

int main() {
//freopen("input.txt", "r", stdin);
while (scanf("%d", &n) == 1 && n) {
init();
_for(i, 0, n) cin >> xl[i] >> yl[i] >> xr[i] >> yr[i];

// then solve()
if(solve(xl, xr, x, n) && solve(yl, yr, y, n)) _for(i, 0, n)
printf("%d %d\n", x[i], y[i]);
else
printf("IMPOSSIBLE\n");

// while finished
}
}