前言

碎碎念

每日一题的计划正在不断优化！
虽说是每日一题，但是刷起兴致了说不定就会变成两题甚至三题呢。
要不改成每日算法题？笑）
还有就是，对于题解的撰写，也越来越清晰了，
要写重要的，写思路，写关键代码，写踩了什么坑，写能怎么优化！

第二就是，终于是磨完了论文，也算是体会了一下学术牛马的处境了。悲）
花了总计三天？
最长24小时没睡硬给搞起来了 O。o

计划

当然，每日一题模块也得更新啦，不能叫每日一题了，叫每日算法吧。
还有就是，要重新拾起网课了，已经两周没看了。

每日一题

P1116 车厢重组

题目描述

在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢，如果将桥旋转 180 度，则可以把相邻两节车厢的位置交换，用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢按车厢号从小到大排列。他退休后，火车站决定将这一工作自动化，其中一项重要的工作是编一个程序，输入初始的车厢顺序，计算最少用多少步就能将车厢排序。

思路

想一想情况：
最优情况：类似 $a[1, 3, 2]$ 的序列，只需要一次 $swap$ 操作即可。
最坏情况：类似 $a[3,2,1]$ 的序列，需要三次 $swap$ 操作：
1. $a[3,2,1]$ -> $a[2,3,1]$
2. $a[2,3,1]$ -> $a[2,1,3]$
3. $a[2,1,3]$ -> $a[1,2,3]$
看了一眼
似乎就是冒泡？
先直接模拟冒泡行为看看吧？ 数据量不大 $N(≤10000)$

提交 #1 <100pt>

哈哈，我是↑↓。

tmd 我本地的编译器默认行为是设置 0 搞得我调试半天没看出哪里问题。

关键代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void solve() {
    cin >> N;
    int cnt = 0;
    vector<int> v(N);
    for (auto &n : v) cin >> n;
    for (int i = 0; i < N; ++i) {
        for (int j = 1; j < N; ++j) {
            if (v[j] < v[j - 1]) {
                cnt++;
                swap(v[j], v[j - 1]);
            }
        }
    }
    cout << cnt;
}

关键点

逆序对与交换次数的关系

结论

在只能交换相邻元素的情况下，
最少交换次数 = 逆序对数。

为什么逆序对数量等于最少交换次数？

思考这样一个场景：

  • 每次只能交换相邻的两节车厢。
  • 要把所有车厢排成升序。
    那么一个较大的车厢，如果它前面有比它小的车厢，就需要一路往后挪。 每交换一次，它就和它后面的小车厢的逆序对减少一个。
    一次交换，只能消除一个逆序对。
    最终目标是让所有逆序对都消除掉，数组变成升序，所以：

    总交换次数 = 逆序对总数。

所以：在只能交换相邻元素的情况下，每次交换消除1个逆序对，最少交换次数就是逆序对数量。

优化 #1

用冒泡排序时间复杂度是 $O(N^2)$，对于 $N \le 10000$，在极限数据下会超时。
用归并排序可以在 $O(N \log N)$ 时间里统计逆序对数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int MAXN = 1e4 + 5;
int N, a[MAXN], tmp[MAXN];
long long cnt = 0;

void merge_sort(int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else {
            tmp[k++] = a[j++];
            cnt += mid - i + 1; // 关键：逆序对增加
        }
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    for (int p = l; p <= r; ++p) a[p] = tmp[p];
}

后记

用一句通俗易懂的话来说：实际上就是统计要发生多少次交换行为。
用正式一点的话来说：
在本题这种只能交换相邻元素的条件下，
逆序对数量恰好就是最终需要发生的总交换次数。

换句话说，就是统计：

要把所有元素移动到正确位置，总共需要多少次相邻交换操作。

P2676 [USACO07DEC] Bookshelf B

题目描述

Farmer John 最近为奶牛们的图书馆添置了一个巨大的书架，尽管它是如此的大，但它还是几乎瞬间就被各种各样的书塞满了。现在，只有书架的顶上还留有一点空间。

所有 $N(1≤N≤20,000)$ 头奶牛都有一个确定的身高 $H_i​(1≤H_i​≤10,000)$。设所有奶牛身高的和为 $S$。书架的高度为 $B$，并且保证 $1≤B≤S<2,000,000,007$。

为了够到比最高的那头奶牛还要高的书架顶，奶牛们不得不像演杂技一般，一头站在另一头的背上，叠成一座“奶牛塔”。当然，这个塔的高度，就是塔中所有奶牛的身高之和。为了往书架顶上放东西，所有奶牛的身高和必须不小于书架的高度。

显然，塔中的奶牛数目越多，整座塔就越不稳定，于是奶牛们希望在能够到书架顶的前提下，让塔中奶牛的数目尽量少。现在，奶牛们找到了你，希望你帮她们计算这个最小的数目。

思路

贪心算法 + 排序

Commit 1：AC

核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
void solve() {
    cin >> N >> B;
    vector<int> vec(N);
    for (auto &n : vec) cin >> n;
    sort(vec.begin(), vec.end());
    int cnt = 0;
    for (int i = N - 1; i >= 0; --i) {
        if (B <= 0) break;
        B -= vec[i];
        cnt++;
    }
    cout << cnt << '\n';
}

优化

没什么可以优化的地方了
不过可以这样写：

1
sort(vec.begin(), vec.end(), greater<int>());

或

1
sort(vec.rbegin(), vec.rend());

P1781 宇宙总统

题目描述

地球历公元 6036 年，全宇宙准备竞选一个最贤能的人当总统，共有 n 个非凡拔尖的人竞选总统，现在票数已经统计完毕，请你算出谁能够当上总统。

票数可能会很大，可能会到 100 位数字，且 $1≤n≤20$ 。

思路

基本思路：高精度 + 排序
高精度 -> 大数string
排序 -> 基排？手写比较器？

所以思路很清晰了 手写string比较器

1. 60pt

只过了 60% 的点
原来是没注意到 自己的 逻辑错误了，从末尾往前比了。

2. AC

关键代码

1
2
3
4
5
6
7
8
9
10
11
12
13
bool cmp(pair<string, int> &pa, pair<string, int> &pb) {
    string &a = pa.first, &b = pb.first;
    // 1. 按长度降序
    if (a.size() != b.size()) {
        return a.size() > b.size();
    }
    // 2. 等长时，直接用 lexicographical compare
    if (a != b) {
        return a > b;  // 字符串 operator> 默认是从前往后比较
    }
    // 3. 完全相同时，保证编号小的优先
    return pa.second < pb.second;
}

关键点

  1. 大数string 高位在开头，别老是粗心搞错
  2. cpp中不需要循环比较，本身对于string就重载了比较符号，基于字典序比较（lexicographical compare）

优化

优化一：lambda

1
2
3
4
5
6
    sort(v.begin(), v.end(), [](pair<string, int> &a, pair<string, int> &b) {
        if (a.first.length() != b.first.length())
            return a.first.length() > b.first.length();
        if (a.first != b.first) return a.first > b.first;
        return a.second < b.second;
    });

优化二：pair支持重载符号

std::pair 在标准库里已经给你实现好了所有的比较运算符（==, !=, <, <=, >, >=），它们的行为都是先比较 .first，如果 .first 相等再比较 .second
所以：

1
2
if (a.first != b.first) return a.first > b.first;
return a.second < b.second;

等价于

1
return a < b;

P1059 [NOIP 2006 普及组] 明明的随机数

题目描述

明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了 N 个 1 到 1000 之间的随机整数 (N≤100)，对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。

思路

value(N) 在 $[1, 1000]$ 之间 直接 选择鸡排。

P1093 [NOIP 2007 普及组] 奖学金

题目描述

某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前 5 名学生发奖学金。期末，每个学生都有 3 门课的成绩：语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学排在前面，这样，每个学生的排序是唯一确定的。

任务：先根据输入的 3 门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前五名名学生的学号和总分。

注意，在前 5 名同学中，每个人的奖学金都不相同，因此，你必须严格按上述规则排序。例如，在某个正确答案中，如果前两行的输出数据（每行输出两个数：学号、总分) 是：

1
2
7 279  
5 279

这两行数据的含义是：总分最高的两个同学的学号依次是 7 号、5 号。这两名同学的总分都是 279 (总分等于输入的语文、数学、英语三科成绩之和) ，但学号为 7 的学生语文成绩更高一些。

如果你的前两名的输出数据是：

1
2
5 279  
7 279

则按输出错误处理，不能得分。

思路

定义一个学生结构体，然后手写一个比较器，
直接用sort排序后输出前五位，
要注意学生数可能不足五位。

核心代码

1
2
3
4
5
6
7
bool cmp(const stu& s1, const stu& s2) {
    int sc1 = s1.c + s1.m + s1.e;
    int sc2 = s2.c + s2.m + s2.e;
    if (sc1 != sc2) return sc1 > sc2;
    if (s1.c != s2.c) return s1.c > s2.c;
    return s1.num < s2.num;
}

补充

当然，也可以直接用lambda函数。

P1923 【深基9.例4】求第 k 小的数

思路

题目要求$O(n)$，所以需要利用分治思想

关键代码

1
2
3
4
5
6
7
8
9
10
11
void qsort(int l,int r) {
    int i = l, j = r, mid = x[(l + r)/ 2];
    do {
        while (x[j] > mid) j--;
        while (x[i] < mid) i++;
        if(i<=j) swap(x[i++],x[j--]);
    } while(i <= j);
    if (k <= j) qsort(l, j);
    else if (i<=k) qsort(i, r);
    else cout << x[j + 1];
}

亮点

  1. qsort中，采用了 do while 的结构，使得可以复用 j 不用写额外逻辑
  2. 对于快排而言 在一次分区之后 会出现 三个区域 $range(num < mid)$、$range(num = mid)$ 和 $range(num >mid)$ 我们只搜索 k 可能存在的区域

错误

  1. 忘记优化IO了，第一次被卡IO卧槽

P1177 【模板】排序

题目描述

将读入的 $N$ 个数从小到大排序后输出。

输入格式

第一行为一个正整数 $N$。

第二行包含 $N$ 个空格隔开的正整数 $a_i$，为你需要进行排序的数。

输出格式

将给定的 $N$ 个数从小到大输出，数之间空格隔开，行末换行且无空格。

输入输出样例 #1

输入 #1

1
2
5
4 2 4 5 1

输出 #1

1
1 2 4 4 5

说明/提示

对于 $20%$ 的数据，有 $1 \leq N \leq 10^3$；

对于 $100%$ 的数据，有 $1 \leq N \leq 10^5$，$1 \le a_i \le 10^9$。

思路

排序模板题，纯练习排序模板了，
练练三大排序吧。

确实是生疏了，写了好一会，不过也学到了新的调试方法：

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
#include <bits/stdc++.h>
using namespace std;
using u64 = unsigned long long;
using i64 = long long;
using f64 = double;
#define all(x) (x).begin(), (x).end()
#define pb(x) push_back(x)
int N;
vector<int> merge(vector<int> &l, vector<int> &r) {
    int i = 0, j = 0, k = 0;
    vector<int> ret(l.size() + r.size());
    while (i < l.size() && j < r.size()) {
        if (l[i] <= r[j]) ret[k++] = l[i++];
        else ret[k++] = r[j++];
    }
    while (i < l.size()) ret[k++] = l[i++];
    while (j < r.size()) ret[k++] = r[j++];
    #ifdef LOCAL
    {
        cout << " value ret : \n";
        for (int i = 0; i < ret.size(); cout << ret[i++] << '\n');
    }
    #endif
    return ret;
}

vector<int> merge_sort(vector<int> &v, int l, int r) {
    if (l == r) return vector<int> {v[l]};
    int mid = (r - l) / 2 + l;
    vector<int> left = merge_sort(v, l, mid);
    vector<int> right = merge_sort(v, mid + 1, r);
    return merge(left, right);
}

  

void solve_in_merge_sort() {
    cin >> N;
    vector<int> vec(N);
    for (int i = 0; i < N; cin >> vec[i++]);
    vec = merge_sort(vec, 0, vec.size() - 1);
    for (int i = 0; i < N; cout << vec[i++] << ' ');
}

int main() {
    solve_in_merge_sort();
    return 0;
}

P1271 【深基9.例1】选举学生会

题目描述

学校正在选举学生会成员，有 $n$（$n\le 999$）名候选人，每名候选人编号分别从 $1$ 到 $n$，现在收集到了 $m$（$m \le 2000000$）张选票，每张选票都写了一个候选人编号。现在想把这些堆积如山的选票按照投票数字从小到大排序。

输入格式

输入 $n$ 和 $m$ 以及 $m$ 个选票上的数字。

输出格式

求出排序后的选票编号。

思路

$1 <= n <= 999$，$1 <= m <= 2*10^6$ 一眼鸡排。
遂使用计数排序。
没什么好说的，一遍过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int n, m;
int arr[1000] = {0};

void solve() {
    cin >> n >> m;
    for (int i = 0, temp = 0; i < m; ++i) {
        cin >> temp;
        arr[temp]++;
    }
    for (int i = 0; i < 1000; ++i) {
        while (arr[i]--) {
            cout << i << ' ';
        }
    }
}