首页 > itarticle > 高效算法设计(一)

高效算法设计(一)

admin 11月 14, 2020 0

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

分治算法，快速排序

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 <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]: %dn", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %dn", 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 () {
    // 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 <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]: %dn", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %dn", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;

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

void () {
    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 <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]: %dn", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %dn", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;

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

void () {
    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("0n");
    }
}

贪心算法：若干区间选出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 <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]: %dn", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %dn", 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 () {
    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 %dn", x[i], y[i]);
        else
            printf("IMPOSSIBLEn");
        
        // while finished
    }
}

二分lower_bound()和upper_bound()

LA3506
LA3506

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
 
const int inf = 0x3f3f3f3f;
const int maxn = 4000 + 5;

int n;

int A[maxn], B[maxn], C[maxn], D[maxn];
int sum[maxn*maxn];

void () {
    Set(A, 0);
    Set(B, 0);
    Set(C, 0);
    Set(D, 0);
    Set(sum, 0);
}

int main() {
    //freopen("input.txt", "r", stdin);
    
    int kase;
    scanf("%d", &kase);
    
    while (kase--) {
        init();
        scanf("%d", &n);
        _for(i, 0, n) {
            cin >> A[i] >> B[i] >> C[i] >> D[i];
        }
        
        int k = 0;
        _for(i, 0, n) _for(j, 0, n) sum[k++] = A[i] + B[j];
        
        sort(sum, sum+k);
        
        llong cnt = 0;
        _for(i, 0, n) _for(j, 0, n) {
            cnt += upper_bound(sum, sum+k, -C[i]-D[j]) - lower_bound(sum, sum+k, -C[i]-D[j]);
        }
        printf("%lldn", cnt);
        if(kase) printf("n");
    }
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能