高效算法设计(四)

贪心算法有很多综合的应用
这里主要阐述一下如何在算法设计中
引入一些数学思想和算法分析的思想

训练题目以
《算法竞赛入门经典第二版》中第八章的题目为主

水题

中途相遇法

POJ2782

算法分析, 先把最大和最小的装起来看看行不行?
可以,就把最大最小的装袋,然后R—

1
2
3
[i, R]
R--相当于出队列
i++相当于i出队列

不可以呢?i++, 就是i单独装袋

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int maxn = 100000 + 10;
int n, M;
int l[maxn];

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

_for(i, 0, n) cin >> l[i];
sort(l, l + n, greater<int>());

int ans = 0;
_for(i, 0, n) {
ans++;
if(l[i] + l[n - 1] <= M) n--;
}
cout << ans << endl;
}

暴力枚举

LA6196
LA6196

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const int maxn = 1000 + 10;
int n;

int main() {
freopen("input.txt", "r", stdin);
string D[maxn], P;

while(cin >> n && n) {
_for(i, 0, n) cin >> D[i];
sort(D, D + n);

string L = D[n / 2 - 1], R = D[n / 2];

P = "A";
_for(i, 0, L.size()) {
while(P[i] <= 'Z' && P < L) P[i]++;
if(P[i] <= 'Z' && L <= P && P < R) break;

if(L[i] != P[i]) P[i]--;
P += "A";
}
cout << P << endl;
}
}

区间非连续子序列预处理

有一类问题称为
在区间中选出若干个点(不一定连续), 这若干个点组成的子序列
需要满足一定条件

UVA11491
UVA11491

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
const int maxn = 100000 + 10;
char buf[maxn];
int A[maxn];
int g[maxn][10];
int N, D;

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

void initCal() {
_rep(x, 0, 9) {
int pos = N;
_forDown(i, N - 1, 0) {
if(A[i] == x) pos = i;
g[i][x] = pos;
}
}
}

bool valid(int x, int L, int R, int E) {
// can x valid in [L, R]
return g[L][x] <= R && R - g[L][x] >= E;
}

int selectMax(int L, int R, int E, int& pos) {
_forDown(x, 9, 0) {
if(!valid(x, L, R, E)) continue;
pos = g[L][x];
return x;
}
}

void solve(int E) {
initCal();
int L = 0;
string ans;
while (E--) {
int pos;
ans += selectMax(L, N - 1, E, pos) + '0';
L = pos + 1;
}
cout << ans << endl;
}

int main() {
freopen("input.txt", "r", stdin);
while(scanf("%d%d", &N, &D) == 2 && N && D) {
init();

scanf("%s", buf);
_for(i, 0, N) A[i] = buf[i] - '0';
// input finished

solve(N - D);
}
}

图形旋转问题

LA5237
LA5237

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
const int maxn = 13;

class Point {
public:
int x, y;
Point(int _x = 0, int _y = 0) : x(_x), y(_y) {}

bool operator< (const Point& rhs) const {
return x < rhs.x || (x == rhs.x && y < rhs.y);
}

bool operator== (const Point& rhs) const {
return x == rhs.x && y == rhs.y;
}
};

Point operator+ (const Point& lhs, const Point& rhs) {
return Point(lhs.x + rhs.x, lhs.y + rhs.y);
}

Point operator- (const Point& lhs, const Point& rhs) {
return Point(lhs.x - rhs.x, lhs.y - rhs.y);
}

Point rotate(const Point& s, const Point& r) {
Point dv = s - r;
Point ans = r + Point(dv.y, -dv.x);
return ans;
}

class Line {
public:
Point from, to;
bool vertical;

Line rot(const Point& r) {
Line ret;
ret.from = ::rotate(from, r);
ret.to = ::rotate(to, r);
return ret;
}

void normalize() {
vertical = (from.x == to.x);
if(vertical) {
if(from.y > to.y) swap(from.y, to.y);
}
else {
if(from.x > to.x) swap(from.x, to.x);
}
}
};

int n;
vector<Line> lines;

void init() {
lines.clear();
}

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

Line l;
l.to = Point(1, 0);
l.vertical = false;

lines.push_back(l);

int minY = l.from.y, maxY = l.from.y;
int minX = l.from.x, maxX = l.to.x;
// debug(maxX);

Point st = l.from, rt = l.to;
// s rotate around r

//debug(lines.size());
_for(i, 0, n) {
int sz = lines.size();
_for(j, 0, sz) {
Line nl = lines[j].rot(rt);
nl.normalize();
lines.push_back(nl);
// debug(lines.size());
}
rt = rotate(st, rt);
}

// rotate finished

map<Point, char> mp;
_for(i, 0, lines.size()) {
Point& lp = lines[i].from;
lp.x *= 2;
if(lines[i].vertical) lp.x--;

minX = min(minX, lp.x);
maxX = max(maxX, lp.x);
minY = min(minY, lp.y);
maxY = max(maxY, lp.y);

//debug(maxY);
//debug(maxX);

mp[lp] = lines[i].vertical ? '|' : '_';
}

// output
// debug(minX);
string buf;
_forDown(y, maxY, minY) {
buf.clear();
_rep(x, minX, maxX) {
Point cur(x, y);
if(mp.count(cur)) buf += mp[cur];
else buf += ' ';
}
while(*(buf.rbegin()) == ' ') buf.erase(buf.size() - 1);
cout << buf << endl;
}
cout << '^' << endl;
}
}

求最小操作次数

LA6152

LA6152

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
string S, T;
int diff[2][2];

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

int solve() {
int q0 = 0, q1 = 0;
int ans = 0;

_for(i, 0, S.size()) if(S[i] != T[i]) {
if(S[i] == '0') diff[0][1]++;
if(S[i] == '1') diff[1][0]++;
if(S[i] == '?' && T[i] == '0') q0++;
if(S[i] == '?' && T[i] == '1') q1++;
}

int x = min(diff[0][1], diff[1][0]);
ans = x + q0;
diff[0][1] -= x;
diff[1][0] -= x;

if(diff[1][0] > q1) return -1;
ans += diff[1][0] + diff[0][1] + q1;
return ans;
}

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

for(int t = 1; cin >> S >> T; t++) {
init();
int ans = solve();
printf("Case %d: %d\n", t, ans);
}
}

二分思想处理冒泡排序

想办法找到i这个位置应该放置的数
然后pos[i] => i,进行归位

LA6588
LA6588

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
const int maxn = 100000 + 10;
int n, arr[maxn];

vector<pair<int, int> > vec;

void init() {
Set(arr, 0);
vec.clear();
}

int Find(int x) {
_rep(i, 1, n) if(arr[i] == x) return i;
return -1;
}

void swapSeg(int from, int to) {
// [from, to]
int len = to - from + 1;
_for(i, 0, len / 2) swap(arr[from + i], arr[from + len / 2 + i]);

vec.push_back(make_pair(from, to));
}

void solve() {
_rep(i, 1, n) {
if(arr[i] == i) continue;
int pos = Find(i);
int to = i + (pos - i) * 2 - 1;

while (to > n) {
int len = pos - i + 1;
if(len % 2) swapSeg(i + 1, pos);
else swapSeg(i, pos);

pos = Find(i);
to = i + (pos - i) * 2 - 1;
}
swapSeg(i, to);
}
}

int main() {
freopen("input.txt", "r", stdin);
int kase;
scanf("%d", &kase);

while (kase--) {
init();
scanf("%d", &n);
_rep(i, 1, n) scanf("%d", &arr[i]);

solve();
printf("%lu\n", vec.size());
_for(i, 0, vec.size()) printf("%d %d\n", vec[i].first, vec[i].second);
}
}

环形链表型的冒泡排序

UVA11925
UVA11925

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
vector<int> cmd, A;
int n;

void init() {
cmd.clear();
A.clear();
}

bool ok() {
_for(i, 0, n) {
if(A[i] != i + 1) return false;
}
return true;
}

int main() {
freopen("input.txt", "r", stdin);
while(scanf("%d", &n) == 1 && n) {
init();

int x;
_for(i, 0, n) {
scanf("%d", &x);
A.push_back(x);
}
// input finished, then solve

if(n == 1) {
puts("");
continue;
}

while(true) {
if(ok()) break;

if(A[0] > A[1] && A[0] != n) {
swap(A[0], A[1]);
cmd.push_back(1);
} else {
A.insert(A.begin(), A[n - 1]);
A.resize(n);
cmd.push_back(2);
}
}

_forDown(i, cmd.size() - 1, 0) printf("%d", cmd[i]);
printf("\n");
}
}

过滤排序(冒泡排序的变形)

其实从冒泡排序的思想出发
还可以引伸出一种排序
叫filter sort(过滤排序)

算法思想如下
filterSort