排序

待排序数组：

1
std::vector<int> target = {123, 4354, 123, 454, 876, 2, 5464};

选择排序

从待排序队列中选出目标值（最大 / 最小值），放在待排序队列最前面，并将该值剔除出待排序队列，该队列前面的队列被视为已排序队列；递归 / 迭代执行该操作，直到待排序队列长度为 0。

1
2
3
4
5
6
7
8
9
template<typename T, typename Comp>
void Sort::choose(std::vector<T> &arr, Comp cmp) {
    for (int i = 0; i < arr.size(); i++) {
        int max = i;
        for (int j = i + 1; j < arr.size(); j++) {
            if (cmp(arr[j], arr[max])) std::swap(arr[j], arr[max]);
        }
    }
}

冒泡排序

从待排序队列中取两个相邻值进行比较，如果其中一个较大（较小），交换二者位置。递归 / 迭代执行，直到遍历至最后一个元素。

1
2
3
4
5
6
7
8
9
10
template<typename T, typename Comp>
void Sort::bubble(std::vector<T> &arr, Comp cmp) {
    for (int i = 0; i < arr.size(); i++) {
        for (int j = 0; j < arr.size() - i - 1; j++) {
            if (!cmp(arr[j], arr[j + 1])) {
                std::swap(arr[j], arr[j + 1]);
            }
        }
    }
}

插入排序

取待排序队列的第一个元素，插入至已排序队列的某两个元素之间，其中这两个元素满足一个大于等于目标元素，另一个小于等于目标元素，并从待排序队列中剔除目标元素。递归 / 迭代执行该操作，直至待排序队列长度为 0。

1
2
3
4
5
6
7
8
9
10
11
template<typename T, typename Comp>
void Sort::insert(std::vector<T> &arr, Comp cmp) {
    for (int i = 1; i < arr.size(); i++) {
        int now = arr[i], j = i - 1;
        for ( ; j >= 0; j--) {
            if (!cmp(arr[j], now)) arr[j + 1] = arr[j];
            else break;
        }
        arr[j + 1] = now;
    }
}

快速排序

递归进行以下操作：

  1. 取序列中的“哨兵”数pivot（通常为中间的那个值）
  2. 将序列中比“哨兵”小（大）的全部放在其左边，反之放在右边；
  3. 将左右两个序列分别视为子序列，继续递归进行这些操作。

直到子序列长度为 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template<typename T, typename Comp>
void Sort::quick(std::vector<T> &arr, Comp cmp) {
    auto s = [&](auto&& self, int l, int r) -> void {
        int pivot = arr[(r + l) / 2];
        int i = l, j = r;
        do {
            while (cmp(arr[i], pivot)) i++;
            while (cmp(pivot, arr[j])) j--;
            if (i <= j) {
                std::swap(arr[i], arr[j]);
                i++, j--;
            }
        } while (i <= j);
        if (i < r) self(self, i, r);
        if (l < j) self(self, l, j);
    };
    s(s, 0, arr.size() - 1);
}

习题

习题 9 - 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
#include <algorithm>
#include <iostream>
#include <vector>

void solve();

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int t = 1;
    // std::cin >> t;
    while (t--) {
        solve();
    }
}

void solve() {
    int n, b;
    std::cin >> n >> b;
    std::vector<int> h(n);
    for (int i = 0; i < n; i++) std::cin >> h[i];
    std::sort(h.begin(), h.end(), [](auto &a, auto &b) { return a > b; });
    int i = 0, sum = 0;
    for ( ; i < n; ++i) {
        sum += h[i];
        if (sum >= b) break;
    }
    std::cout << i + 1 << std::endl;
}

习题 9 - 2

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
#include <algorithm>
#include <iostream>
#include <vector>

void solve();

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int t = 1;
    // std::cin >> t;
    while (t--) {
        solve();
    }
}

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> arr(n);
    for (int i = 0; i < n; i++) std::cin >> arr[i];
    int a = 0;
    auto bubble = [&] {
        for (int i = 0; i < arr.size(); i++) {
            for (int j = 0; j < arr.size() - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    std::swap(arr[j], arr[j + 1]);
                    a++;
                }
            }
        }
    };
    bubble();
    std::cout << a << '\n';
}

习题 9 - 3

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
#include <iostream>
#include <set>
#include <vector>

void solve();

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int t = 1;
    // std::cin >> t;
    while (t--) {
        solve();
    }
}

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> arr(n);
    for (int i = 0; i < n; i++) std::cin >> arr[i];
    std::set<int> set;
    for (int i = 0; i < n - 1; i++) {
        set.insert(std::abs(arr[i] - arr[i + 1]));
    }
    for (int i = 1; i < n; i++) {
        if (set.find(i) == set.end()) {
            std::cout << "Not jolly" << std::endl;
            return;
        }
    }
    std::cout << "Jolly" << std::endl;
}

习题 9 - 4

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
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>

void solve();

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int t = 1;
    // std::cin >> t;
    while (t--) {
        solve();
    }
}

void solve() {
    int m, n;
    std::cin >> n >> m;
    std::vector<std::pair<int, int>> people;
    for (int i = 0; i < n; i++) {
        int u, v;
        std::cin >> u >> v;
        people.emplace_back(u, v);
    }
    std::sort(people.begin(), people.end(), [](auto p1, auto p2) {
        if (p1.second != p2.second) return p1.second > p2.second;
        return p1.first < p2.first;
    });
    int zz = std::floor(m * 1.5);
    int fl = people[zz - 1].second;
    for ( ; zz < people.size(); zz++) {
        if (people[zz - 1].second != fl) break;
    }
    zz--;
    std::cout << people[zz - 1].second << ' ' << zz << std::endl;
    for (int i = 0; i < zz; i++) std::cout << people[i].first << ' ' << people[i].second << std::endl;
}

习题 9 - 5

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
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <vector>

void solve();

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int t = 1;
    // std::cin >> t;
    while (t--) {
        solve();
    }
}

void solve() {
    int n;
    std::cin >> n;
    struct Point {int x; int y; int z;};
    std::vector<Point> arr(n);
    for (int i = 0; i < n; i++) std::cin >> arr[i].x >> arr[i].y >> arr[i].z;
    std::sort(arr.begin(), arr.end(), [](auto &a, auto &b) {
        return a.z < b.z;
    });
    double d = 0;
    auto D = [](Point& a, Point& b) {
        return std::sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) + (a.z - b.z) * (a.z - b.z));
    };
    for (int i = 0; i < n - 1; i++) {
        d += D(arr[i], arr[i + 1]);
    }
    std::cout << std::fixed << std::setprecision(3) << d << std::endl;
}

习题 9 - 6

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
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <vector>

void solve();

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int t = 1;
    // std::cin >> t;
    while (t--) {
        solve();
    }
}

void solve() {
    int n;
    std::cin >> n;
    struct Birthday {int year; int month; int day;};
    
    struct Person {
        std::string name;
        Birthday b;
        int idx;
    };

    std::vector<Person> people(n);

    for (int i = 0; i < n; i++) {
        std::cin >> people[i].name 
                 >> people[i].b.year 
                 >> people[i].b.month 
                 >> people[i].b.day;
        people[i].idx = i;
    }

    std::sort(people.begin(), people.end(),
        [](const Person &a, const Person &b) {
            if (a.b.year != b.b.year) return a.b.year < b.b.year;
            if (a.b.month != b.b.month) return a.b.month < b.b.month;
            if (a.b.day != b.b.day) return a.b.day < b.b.day;
            return a.idx > b.idx;
        }
    );
    for (auto &p : people)
        std::cout << p.name << "\n";
}

习题 9 - 7

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
#include <algorithm>
#include <iostream>
#include <vector>

void solve();

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int t = 1;
    // std::cin >> t;
    while (t--) {
        solve();
    }
}

void solve() {
    int n;
    std::cin >> n;

    std::vector<std::string> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    sort(a.begin(), a.end(), [](const std::string &x, const std::string &y) {
        return x + y > y + x;
    });

    if (a[0] == "0") {
        std::cout << 0;
        return;
    }

    for (auto &s : a) std::cout << s;
}
License

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

快来参与讨论吧~