算法作业题

算法作业记录

担心很多东西学过就忘了，就写 blog 加深印象和后期回顾

Work 1 (摸底作业)

1.求最小生成树的Prim算法

题目描述：

请编写程序，实现在带权的无向图中求最小生成树的 Prim 算法。 注意：当多个待收录顶点到当前点集的距离等长时，按编号升序进行收录。

输入格式：

输入首先在第一行给出两个正整数，依次为当前要创建的图的顶点数 n（≤100）和边数 m。 随后 m 行，每行给出一条无向边两端点的编号、权重。顶点编号从 0 开始，权重（≤100）为整数。同行数字均以一个空格分隔。

输出格式：

参考样例。 首先在一行中输出 total weight = x，其中 x 为最小生成树中所有边的总权重。如果最小生成树不存在，则 x 为 −1。 随后在一行中按顶点编号升序输出每个顶点在最小生成树中的父结点的编号。为输出简单起见，每个数字后有一个空格。 注意：此处默认顶点 0 为最小生成树的根结点，其父结点编号规定为 −1。算法初始化时，所有顶点（除了根结点）的父结点编号默认为 0。

输入样例 1：

6 9
0 1 1
0 2 3
1 2 6
1 3 2
2 3 7
2 4 5
2 5 4
3 5 8
4 5 1

输出样例 1：

total weight = 11
-1 0 0 1 5 2 

输入样例 2：

7 9
0 1 1
0 2 3
1 2 6
1 3 2
2 3 7
2 4 5
2 5 4
3 5 8
4 5 1

输出样例 2：

total weight = -1
-1 0 0 1 5 2 0 

这题就是 prim算法 的模板题，需要注意的是图一定要用邻接表储存，空间: $O(n + m)$；邻接矩阵存储，空间: $O(n \times m)$，这个内存是会爆的

解题代码(Eager Prim)：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;

vector<int> res;
int prim(int n, const vector<vector<pii>>& adj) {
    vector<int> dist(n, INF);
    vector<int> parent(n, 0);
    vector<bool> visited(n, false);
    priority_queue<pii, vector<pii>, greater<pii>> pq;

    dist[0] = 0;
    parent[0] = -1;
    pq.push({0, 0});

    int cost = 0, cnt = 0;
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (visited[u]) continue;

        visited[u] = true;
        cost += d;
        cnt++;

        for (auto& edge: adj[u]) {
            auto [v, w] = edge;
            if (!visited[v] && w < dist[v]) {
                dist[v] = w;
                parent[v] = u;
                pq.push({w, v});
            }
        }
    }

    res = move(parent);
    return (cnt == n) ? cost : -1;
}

int main()
{
    int n, m;
    cin >> n >> m;

    vector<vector<pii>> adj(n);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w}); // 无向图，别忘了加边
    }

    cout << "total weight = " << prim(n, adj) << endl;
    for (auto num : res) cout << num << " ";
    cout << endl;

    return 0;
}

顺便介绍一下 Lazy Prim，就是 Eager Prim 的去 dist数组 版，相比 Eager Prim 逻辑不同的是最小堆存储的是边，而不是点，代码如下：

typedef pair<int, int> pii;

struct edge{
    int u, v, w;

    auto operator<=>(const edge& other) const {
        if (w != other.w) return w <=> other.w;
        if (v != other.v) return v <=> other.v;
        return u <=> other.u;
    }

    bool operator==(const edge& other) const = default;
};

vector<int> res;
int prim(int n, const vector<vector<pii>>& adj) {
    vector<bool> visited(n, false);
    vector<int> parent(n, 0);
    priority_queue<edge, vector<edge>, greater<edge>> pq;

    visited[0] = true;
    for (const auto& [v, w]: adj[0]) pq.push({0, v, w});
    parent[0] = -1;

    int cost = 0, cnt = 1;
    while (!pq.empty()) {
        auto [start, end, d] = pq.top();
        pq.pop();

        if (visited[end]) continue;

        visited[end] = true;
        cost += d;
        parent[end] = start;
        cnt++;

        for (auto& [v, w]: adj[end]) if (!visited[v]) pq.push({end, v, w});
    }

    res = move(parent);
    return (cnt == n) ? cost : -1;
}

注意：

• 实际上 Eager Prim 是最常用的，因为 Lazy Prim 的时间、空间复杂度都要高于 Eager (尤其是空间，在边数大的情况下可能会栈溢出)，这里写出仅是展示不同思路

• 这题有严格的 tie_break 限制：

  当多个待收录顶点到当前点集的距离等长时，按编号升序收录。

  • 但是优先队列(priority_queue)底层是二叉堆，只保证堆顶是最小/最大，不会维护相同优先级元素的相对顺序，所以 priority_queue 是不稳定的

  • 于是当优先级完全相同(边权和指向点相同)时优先队列无法保证先进先出，于是这道题只能用 Eager，Lazy 会卡一个测试点

2.最短路的交点

题目描述：

给定有向加权图 G，和 4 个顶点 u, v, s, t。假设图 G 中所有边的权值都非负。设计一个算法来判定“从 u 到 v 的最短路径”和“从 s 到 t 的最短路径”是否存在一个交点 w。也即，顶点 w 是 u 到 v 的最短路径上的一个顶点，同时也是 s 到 t 的最短路径上的一个顶点。 注意：最短路径包含两个端点；一对顶点间的最短路径可能不止一条，求交点时必须将所有最短路径考虑在内。

输入格式：

输入第 1 行给出 6 个正整数，依次为：n（≤1000，图中顶点数）、m（≤3000，图中边数）、题面中描述的 4 个顶点 u, v, s, t 的编号。这里假设顶点从 1 到 n 编号，并且 u, v, s, t 的编号均不相同。 随后 m 行，每行给出一条有向边的起点编号、终点编号、非负权重（≤100）。题目保证每条边都不会重复给出，同行数字间以空格分隔。

输出格式：

在一行中，按编号递增的顺序输出所有交点。数字间以 1 个空格分隔，行首尾不得有多余空格。如果交点不存在，则在一行中输出 No Intersection

输入样例 1：

6 7 1 2 3 4
1 2 3
1 5 1
3 5 1
5 6 1
5 4 2
6 4 1
6 2 1

输出样例 1：

5 6

输入样例 2：

4 4 1 2 3 4
1 2 1
3 4 1
1 4 1
3 2 1

输出样例 2：

No Intersection

解释：

• 本题主要考察 dijkstra算法及其性质 的应用

• dijkstra算法 ：求该点到图中其它点的的最短路径长度， 二叉堆优化实现时间复杂度: $O((V+E)\log V)\approx O(E\log V)$，其中 V, E 分别是顶点数、边数

• dist_u[v]表示u 到 v 的最短路径距离，记 w 为其它点，若 dist_u[w] + dist_w[v] = dist_u[v]，则表明 w 在 u->v 的最短路径上

  • 对于 dist_u[w] 和 dist_u[v] 只需要对 u 跑一次 dijkstra 即可得到

  • 对于 dist_w[v]，我们不可能对所有点跑 dijkstra 得到所有点的 dist_x[v]，其中 x 代表任意一点，因为时间复杂度为 $O(V\cdot E\cdot \log V)$，效率太低

• 于是我们不求每个点到 v 的最短路径长度，而是求 v 到各个点的最短路径长度，于是我们构建反图，即代码(main函数)中 rev

  • 因为这是有向图，所以原图若有 u->v，则反图应有 v->u，因为两者的路径长度是相同的，均为 w

  • 所以所有点到 v 的最短路径长度可以转为反图中 v 到各点的的最短路径长度(即从n次dijkstra减少到1次)

• 得到 u, v, s, t 点的 dijkstra 结果数组后即可遍历各点判断交点

注意：

• INF 一定不能参与判断逻辑，否则会被卡一个1分的测试点

• 对应代码块：(同时也是核心判断逻辑)

if (dist_u[i] != INF && dist_v[i] != INF &&
    dist_s[i] != INF && dist_t[i] != INF &&
    dist_u[i] + dist_v[i] == dist_u[v] && 
    dist_s[i] + dist_t[i] == dist_s[t]) 
            
    res.push_back(i);

解题代码：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;

vector<int> dijkstra(int n, int start, const vector<vector<pii>>& adj) {
    vector<int> dist(n + 1, INF);
    priority_queue<pii, vector<pii>, greater<pii>> pq;

    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (d > dist[u]) continue;

        for (auto [v, w]: adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }

    return dist;
}

int main()
{
    int n, m, u, v, s, t;
    cin >> n >> m >> u >> v >> s >> t;

    vector<vector<pii>> adj(n + 1), rev(n + 1);
    for (int i = 0; i < m; i++) {
        int x, y, w;
        cin >> x >> y >> w;

        adj[x].push_back({y, w});
        rev[y].push_back({x, w});
    }

    auto dist_u = dijkstra(n, u, adj);
    auto dist_v = dijkstra(n, v, rev);
    auto dist_s = dijkstra(n, s, adj);
    auto dist_t = dijkstra(n, t, rev);

    vector<int> res;

    for (int i = 1; i <= n; i++) {
        if (dist_u[i] != INF && dist_v[i] != INF &&
            dist_s[i] != INF && dist_t[i] != INF &&
            dist_u[i] + dist_v[i] == dist_u[v] && 
            dist_s[i] + dist_t[i] == dist_s[t]) 
            
            res.push_back(i);
    }

    if (res.empty()) {
        cout << "No Intersection";
    } else {
        for (int i = 0; i < res.size(); i++) {
            if (i == res.size() - 1) cout << res[i];
            else cout << res[i] << " ";
        }
    }
    cout << endl;
    
    return 0;
}

3.强连通分量

题目描述：

本题请你编写程序，输出给定有向图中的各个强连通分量，并统计强连通分量的个数。

输入格式：

输入首先在第一行给出 2 个整数，依次为有向图的顶点数 n（0<n≤15）和边数 m。 随后 m 行，每行给出一条有向边的起点和终点编号。编号从 0 开始，其间以 1 个空格分隔。

输出格式：

按照 { v1 v2 ... vk } 的格式，每行输出一个强连通分量中的所有顶点 v1 ~ vk 的编号。最后一行输出强连通分量的个数。

输入样例：

4 5
0 1
1 3
3 0
2 1
2 3

输出样例：

{ 0 1 3 }
{ 2 }
2

注意： 强连通分量的输出顺序是不唯一的，以任何顺序输出都可以，有特殊裁判程序判断输出的正确性。例如下列输出也是正确的。

{ 2 }
{ 1 3 0 }
2

解释：

• 此题主要考察 tarjan算法 应用

• tarjan: 用一次 dfs 找出所有强连通分量

  • 主要维护 dfn数组, low数组, st栈

  • 主要讨论新增边为树边和回边的情况

具体原理学习 Click Here

解题代码：

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

const int N = 16;
vector<int> dfn(N, 0), low(N, 0);
vector<bool> inStack(N, false);
stack<int> st;
vector<vector<int>> adj(N);

int timer = 0, scc_cnt = 0;

void tarjan(int u) {
    dfn[u] = low[u] = ++timer;
    st.push(u);
    inStack[u] = true;

    for (auto v : adj[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = std::min(low[u], low[v]);
        } else if (inStack[v]) {
            low[u] = std::min(low[u], dfn[v]);
        }
    }

    if (dfn[u] == low[u]) {
        scc_cnt++;

        cout << "{ ";
        while (true) {
            int top = st.top();
            st.pop();
            inStack[top] = false;

            cout << top;
            if (top == u) break;
            cout << " ";
        }
        cout << " }" << endl;
    }
}

int main()
{
    int n, m;
    cin >> n >> m;


    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }

    for (int i = 0; i < n; i++) if (!dfn[i]) tarjan(i);
    cout << scc_cnt << endl;

    return 0;
}

4.国际影响力代价计算

题目描述：

一个国家对另一个国家的影响力，与其自身实力相关，也与两国间的距离相关。在此我们做一个超级简化的国际关系模型，将所有国家排列在一个 n 行 m 列的矩阵中，并简单假设国家 A 要影响国家 B 所需要付出的代价：

$$ C_{AB} = S_A \times dist(A,B) $$

其中：

• S_A 是国家 A 自身的实力

• dist(A,B) 是国家 A 和国家 B 之间的距离

为简化计算，定义：

$$ dist(A,B) = \max(|i_A - i_B|, |j_A - j_B|) $$

其中 $i_x$ 和 $j_x$ 为国家 x 所在位置的行号和列号（从 1 开始）。

本题请你计算 每个国家要影响全球所有国家所需要付出的总代价。

输入格式：

输入首先在第一行给出两个正整数 n 和 m（1 ≤ m n ≤ 10^6），为国家矩阵的行数和列数。

随后 n 行，每行给出 m 个不超过 $10^6$ 的正整数，依次代表对应位置上国家的自身实力。同行数字间以空格分隔。

输出格式：

输出 n 行，每行 m 个正整数，依次代表对应位置上的国家要影响全球所有国家所需要付出的总代价。

同行数字间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：

3 3
2 5 7
9 4 1
3 6 8

输出样例：

26 55 91
99 32 11
39 66 104

前置知识点：

1. 欧几里得距离：

含义：两点间直线距离

公式：$d = \sqrt {(x_1 - x_2)^2 + (y_1 - y_2)^2}$

函数公式：$|x| + |y| = |d|$，图片中取 $d = 2$

图片：

2. 曼哈顿距离：

含义：只能横平竖直走的距离

公式：$d = |x_2 - x_1| + |y_2 - y_1|$

函数：$|x| + |y| = d$

图片：

3. 切比雪夫距离：

含义：两点之间横纵坐标差中的较大值

公式：$d = \max (|x_2 - x_1|,|y_2 - y_1|)$

函数：$\lim_{p \to \infty} (|x|^p + |y|^p = d^p)$，实际上当 $p \to \infty$ 时图形为正方形，图片中取 $p = 100$ 方便直观感受

图片：

分析：

题中就是求从所有点到一点的 切比雪夫距离 之和，即

$$ S_A \times \sum_B dist(A, B) $$

，核心就是求 $\sum_B dist(A, B)$

如果暴力计算时间复杂度将达到 $O((nm)^2)$，最大 $10^{12}$，因此我们要想办法把 $\max(|dx|, |dy|)$ 变为容易处理的形式

• 常见技巧：坐标旋转 $45^{\circ}$，将二维的 切比雪夫距离 拆成两个一维的 曼哈顿距离

• 数学变换过程：

  核心公式：

  $$ \max(x,y) = \frac {\left|x+y\right| + \left|x-y\right|}{2} $$

  题目中定义：$dist(A,B) = \max(\left|i_A - i_B\right|, \left|j_A - j_B\right|)$

  令 $dx = i_A - i_B,\ dy = j_A - j_B$，则有

  $$ dist(A,B) = \frac {\left|dx + dy\right| + \left|dx - dy\right|}{2} $$

  再定义坐标变换 $u = i + j,\ v = i - j$，则

  $$ \begin{aligned} |dx + dy| &= |u_A - u_B|\\ |dx - dy| &= |v_A - v_B| \end{aligned} $$

  ，因此 $$ dist(A,B) = \frac {\left|u_A - u_B\right| + \left|v_A - v_B\right|}{2} $$

  ，于是 $$ \sum_B dist(A,B) = \frac {\sum_B \left|u_A - u_B\right| + \sum_B \left|v_A - v_B\right|}{2} $$

  几何解释：

  这个变换实际上是 线性变换：

  $$ \begin{pmatrix} u \\ v \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} $$

  几何上相当于：

  1. 坐标轴旋转 $45^{\circ}$ (上面图片可以直观感受到)
  2. 做一个缩放(这里的系数是 $\frac 12$)

  此时，问题变成对所有点计算其它点的绝对值距离和，这可以用 排序 + 前缀和 在 $O(\log n)$ 求出

  u，v 都是一维变量，现在只需求 $\sum \left|x - x_i\right|$

• 如何在一个数组中快速求 $\sum \left|x - x_i\right|$

  定义排序后数组 arr = [1, 2, 3, 4, 6, 7]，N = arr.size() <= 1e6

  若对 arr[3] = 4 求 $\sum \left|x - x_i\right|$，元素4 左边的元素求和得到

  $$ Left = (4 - 1) + (4 - 2) + (4 - 3) = 4 \cdot 3 - (1 + 2 + 3) $$

  即 Left = arr[pos] * pos - prefix[pos]

  此处的 prefix 前缀和数组应为 [0, 1, 3, 6, 10, 16, 23]

  ，定义 totalSum = prefix[N] ，同理右侧元素求和得到

  $$ Right = (6 - 4) + (7 - 4) = (6 + 7) - 4 \cdot 2 $$

  即 Right = (totalSum - prefix[pos + 1]) - arr[pos] * (N - pos - 1)

  $$ \sum \left|x - x_i\right| = Left + Right $$

  至此便算出了一个元素对数组中其他元素的差值的绝对值和

• 桶计数优化：

  $$ \begin{cases} u = i + j \in [0, n + m]\\ v = i - j \in [1 - m, n - 1] \end{cases} $$

  由于 u, v 的值域很小，因此可以采用桶计数(值域小代表空间复杂度小)，即记录每个值出现的次数，并通过前缀和在 $O(1)$ 计算 $\sum \left|x - x_i\right|$

• 时间复杂度分析：(桶计数优化后不需要排序)

  • 前缀和数组计算 $O(n + m)$, 排序位置数组计算 $O(n + m)$

  • 每个元素计算过程时间复杂度为 $O(1)$，所有元素即为 $O(N)$

  • 总时间复杂度为 $O(N)$

解题代码：

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;
using ll = long long;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    int N = n * m;
    int UMAX = n + m + 5, VMAX = n + m + 5;

    vector<ll> S(N), Cost(N);
    vector<int> U(N), V(N);

    // cntU 数组记录数组中 <=u 的数的个数(用前缀和的方式计算)
    // 同理，sumPreU 数组记录当前前缀和
    vector<ll> cntU(UMAX, 0), cntV(VMAX, 0), sumPreU(UMAX, 0), sumPreV(VMAX, 0);
    
    int idx = 0, offset = m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> S[idx];

            int u = i + j;
            int v = i - j + offset;

            U[idx] = u;
            V[idx] = v;
            idx++;

            cntU[u]++;
            cntV[v]++;
        }
    }

    for (int i = 1; i < UMAX; i++) {
        sumPreU[i] = sumPreU[i - 1] + cntU[i] * i;
        cntU[i] += cntU[i - 1];
    }

    for (int i = 1; i < VMAX; i++) {
        sumPreV[i] = sumPreV[i - 1] + cntV[i] * i;
        cntV[i] += cntV[i - 1];
    }

    ll totalSumU = sumPreU[UMAX - 1];
    ll totalSumV = sumPreV[VMAX - 1];
    
    for (int i = 0; i < N; i++) {
        int u = U[i];
        int v = V[i];

        ll ULeft = 1LL * u * cntU[u] - sumPreU[u];
        ll URight = (totalSumU - sumPreU[u]) - 1LL * u * (N - cntU[u]);

        ll VLeft = 1LL * v * cntV[v] - sumPreV[v];
        ll VRight = (totalSumV - sumPreV[v]) - 1LL * v * (N - cntV[v]);

        ll dist = (ULeft + URight + VLeft + VRight);
        Cost[i] = S[i] * dist / 2;
    }

    idx = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (j == m - 1) cout << Cost[idx++];
            else cout << Cost[idx++] << " ";
        }

        cout << "\n";
    }

    return 0;
}

后面的题有点小难，还在努力中...结束了也没写出来

Work 2 (分治专题)

2.货仓选址

题目描述：

在一条数轴上有 N 家商店，它们的坐标分别为 A1~AN。 现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小

输入格式:

第一行输入整数N, 第二行N个整数A1~AN。1≤N≤100000, 0≤Ai≤40000

输出格式:

输出一个整数，表示距离之和的最小值。

输入样例:

4
6 2 9 1

输出样例:

12

分析：

所有点到数轴上一点 $x$ 的距离之和 $S = \sum_{i=1}^{N} \left| A_i - x \right|$，要使得 $S$ 最小，则 $x$ 应为 $A_i$ 的 中位数，为什么呢？

先把坐标排好序，即 $A_1 \leq A_2 \leq \cdots \leq A_N$。

假设货仓的位置建在 $x$，则考虑将货仓 $x$ 往右移一格

• 在 $x$ 左边的商店到货仓的距离都会 +1

• 在 $x$ 右边的商店到货仓的距离都会 -1

所以总距离变化值为 (左边的商店数) - (右边的商店数)

1. 若左边的商店更多，则此时不应该向右移动，否则会使距离总和变大

2. 若右边的商店更多，则此时应该向右移动使总和变小

3. 若两边的商店数一样，则此时左右移动都不会使距离更小

最后会发现：哪里商店多 $x$ 就应该往哪里走，最终落在 中位数 的值上

所以思路就是：

• 先排序

• 找到中位数

• 累加 $\left| A_i - x\right|$ 得到答案

解题代码：

#include <iostream>
#include <vector>
#include <algorithm>

using std::cin;
using std::cout;

using i64 = long long;

int main()
{
    int n;
    cin >> n;
    std::vector<int> arr(n);

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

    std::ranges::sort(arr);
    int middle = arr[n/2];
    
    i64 sum = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] > middle) sum += arr[i] - middle;
        else sum += middle - arr[i];
    }

    cout << sum ;

    return 0;
}

6.输油管道问题

题目描述：

某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n口油井的位置,即它们的x 坐标（东西向）和y 坐标（南北向）,应如何确定主管道的最优位置,即使各油井到主管道之间的输油管道长度总和最小的位置? 证明可在线性时间内确定主管道的最优位置。

给定n口油井的位置, 计算各油井到主管道之间的输油管道最小长度总和。

输入格式:

输入的第1 行是油井数n，1<=n<=10000。接下来n 行是 油井的位置，每行2个用空格割开的整数 x和 y，-10000<=x，y<=10000。

输出格式:

输出油井到主管道之间的输油管道最小长度总和。

输入样例:

5
1 2
2 2
1 3
3 -2
3 3

输出样例:

6

分析：

这与 Work2 - 2 的题目很像，就是求所有点到一条水平线的纵向距离之和 $S = \sum_{i=1}^n \left|y_i - y\right|$ 的最小值，其中 $y$ 是该水平线的纵坐标。

是不是很眼熟？依旧是 排序找中位数。另外，题目所给的横坐标 $x_i$ 是多余的

解题代码：

#include <iostream>
#include <vector>
#include <algorithm>

using std::cin;
using std::cout;

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, x;
    cin >> n;
    std::vector<int> y(n + 1);
    for (int i = 1; i <= n; i++) cin >> x >> y[i];
    std::sort(y.begin() + 1, y.end());

    // 找中位数这里写复杂了，参考第二题写法即可
    int mid;
    if (n & 1) mid = y[(n + 1) >> 1];
    else mid = (y[n >> 1] + y[(n >> 1) + 1]) >> 1;

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (y[i] >= mid) ans += y[i] - mid;
        else ans += mid - y[i];
    }

    cout << ans << '\n';

    return 0;
}

7.士兵排队

题目描述：

在一个划分成网格的操场上，n个士兵散乱地站在网格点上。网格点用整数坐标(x,y)表示。士兵们可以沿网格边往上、下、左、右移动一步，但在同一时刻任一网格点上只能有一名士兵。按照军官的命令，士兵们要整齐地列成一个水平队列，即排列成(x,y),(x+1,y),…,(x+n-1,y)。如何选择x和y的值才能使士兵们以最少的总移动步数排成一行。

编程计算使所有士兵排成一行需要的最少移动步数。

题目引自POJ

输入格式:

第1行是士兵数n，1≤n≤10000。接下来n行是士兵的初始位置，每行有2个整数x和y，-10000≤x，y≤10000。

输出格式:

一个数据，即士兵排成一行需要的最少移动步数。

输入样例:

5
1  2
2  2
1  3
3  -2
3  3

输出样例:

8

分析：

• 首先从纵向来看，最终士兵要站到同一行上，所以要移动到哪一行才能让士兵的纵向移动距离之和最小呢？依然是 中位数！如果此时还没形成条件反射那就得反思了！

• 然后看横向(此题难点)

  • 结论：定义一个新数组 $s$，其中 $s_i = x_i - i + 1$，找到这个数组的 中位数 (设为 $mid_s$)作为基准求出 $\sum_{i=1}^n \left| s_i - mid_s\right|$ 即是横向移动距离之和的最小值

  • 解释：将 $x_i$ 排序，假设士兵排好队后最左边的那名士兵所在的横坐标是 $s$，则士兵1从 $x_1$ 到 $s$，士兵2从 $x_2$ 到 $s+1$，$\cdots$，士兵n从 $x_n$ 到 $s+n-1$。则横向移动的距离之和为

  $$ \left|x_1 - s\right| + \left|x_2 - 1 - s\right| + \cdots + \left|x_n - (n - 1) - s\right| $$

  • 定义 $s_i = x_i - i + 1$，则实际上是在求 $\sum_{i=1}^n \left| s_i - s\right|$ 的最小值，所以依然找 中位数 即可

解题代码：

#include <iostream>
#include <vector>
#include <algorithm>

using std::cin;
using std::cout;

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    cin >> n;
    std::vector<int> x(n + 1), y(n + 1), s(n + 1);
    for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];
    std::sort(x.begin() + 1, x.end());
    std::sort(y.begin() + 1, y.end());

    for (int i = 1; i <= n; i++) s[i] = x[i] - i + 1;
    std::sort(s.begin() + 1, s.end());

    int mid_s, mid_y;
    mid_s = s[(n + 1) >> 1];
    mid_y = y[(n + 1) >> 1];

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (s[i] >= mid_s) ans += s[i] - mid_s;
        else ans += mid_s - s[i];
    }

    for (int i = 1; i <= n; i++) {
        if (y[i] >= mid_y) ans += y[i] - mid_y;
        else ans += mid_y - y[i];
    }

    cout << ans << '\n';

    return 0;
}

3.两个有序序列的中位数

题目描述：

已知有两个非降序序列S1, S2, 求S1与S2归并成一个序列的低位中位数。有序序列 $A_0,A_1,\cdots,A_{N−1}$ 的中位数指 $A_{(N−1)/2}$ 的值,即第 $⌊(N+1)/2⌋$ 个数（A0为第1个数）。S1, S2由输入的序列长度N写代码初始化

for (int i = 0 ; i < n;++i) {
    S1[i]= 2*i+1;//奇数递增序列1，3，5，7…….
    S2[i]= 2*i;//偶数递增序列0，2，4，6，……..
}

输入格式:

第一行给出第一个序列的长度 $N$（$0<N≤2500000$）:输入样例的2500000

第2行给出测试区间组数 $t$ （$0<t<10000$）:输入样例的 $7$ 后面 $t$ 行区间数据，每行分别为空格隔开的4个整数，前2个整数为第一个数组的起始下标lowa和区间元素数目n1，后2个整数为第二个数组的起始下标lowb和区间元素数目n2

样例 0 5 9 5 解释如下：即S1 数组区间 [0, 0+5) 和 S2 数组区间[9,9+5)

即：1，3，5，7，9 和 18，20，22，24，26

求解这2个区间数组的中位数。显然中位数就是9，所以输出结果第一行就是9

样例 9 5 0 5 解释如下：即S1 数组区间 [9, 9+5) 和 S2 数组区间[0,0+5)

即：19，21，23，25，27 和 0，2，4，6，8

求解这2个区间数组的中位数。显然中位数就是8，所以输出结果第二行就是8

输出格式:

依次输出每行区间数据对应2个数组的中位数。

输入样例:

在这里给出一组输入。例如：

25000000
7
0 5 9 5 
9 5 0 5 
0 6 8 6 
0 5 0 8 
0 4 6 9 
0 5 8 8 
9 5 0 6 

输出样例:

在这里给出相应的输出。例如：

9
8
11
6
16
18
10

分析：

这题理解难度不小，不会的话直接看力扣的题解学习

题解点这里

解题代码：

#include <iostream>
#include <vector>
#include <algorithm>

using std::cin;
using std::cout;

inline int getS1(int x) {return (x << 1) | 1;}
inline int getS2(int x) {return x << 1;}

int findKth(int lowa, int n1, int lowb, int n2, int k) {
    if (n1 == 0) return getS2(lowb + k - 1);
    if (n2 == 0) return getS1(lowa + k - 1);
    if (k == 1) return std::min(getS1(lowa), getS2(lowb));

    int pa = std::min(n1, k >> 1);
    int pb = std::min(n2, k >> 1);

    if (getS1(pa + lowa - 1) <= getS2(pb + lowb - 1)) {
        lowa += pa;
        n1 -= pa;
        k -= pa;
    } else {
        lowb += pb;
        n2 -= pb;
        k -= pb;
    }

    return findKth(lowa, n1, lowb, n2, k);
}

int main()
{
    int N, T;
    cin >> N >> T;

    while (T-- > 0) {
        int l1, n1, l2, n2;
        cin >> l1 >> n1 >> l2 >> n2;

        int k = (n1 + n2 + 1) >> 1;
        cout << findKth(l1, n1 ,l2, n2, k) << '\n';
    }

    return 0;
}

4.插入排序还是堆排序

题目描述：

根据维基百科的定义：

插入排序 是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确的位置。如此迭代直到全部元素有序。

堆排序 也是将输入分为有序和无序两部分，迭代地从无序部分找出最大元素放入有序部分。它利用了大根堆的堆顶元素最大这一特征，使得在当前无序区中选取最大元素变得简单。

现给定原始序列和由某排序算法产生的中间序列，请你判断该算法究竟是哪种排序算法？

输入格式：

输入在第一行给出正整数 $n (\leq 100)$；随后一行给出原始序列的 $n$ 个整数；最后一行给出由某排序算法产生的中间序列。这里假设排序的目标序列是升序。数字间以空格分隔。

输出格式：

首先在第 $1$ 行中输出 Insertion Sort 表示插入排序、或 Heap Sort 表示堆排序；然后在第 $2$ 行中输出用该排序算法再迭代一轮的结果序列。题目保证每组测试的结果是唯一的。数字间以空格分隔，且行首尾不得有多余空格。

输入样例1：

10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0

输出样例1：

Insertion Sort
1 2 3 5 7 8 9 4 6 0

输入样例2：

10
3 1 2 8 7 5 9 4 6 0
6 4 5 1 0 3 2 7 8 9

输出样例2：

Heap Sort
5 4 3 1 
0 2 6 7 8 9

分析：

• 首先我们得明确，这题只用判断是否是插入排序即可，若不是插排就是堆排序

• 其次我们没有必要一步步的从头开始模拟插入排序，我们只需比较未排序部分和给定的半排序序列是否相同即可，因为插入排序不会对未排序部分造成影响(稳定性的体现)，而堆排序会频繁且剧烈地打乱原数组的相对顺序

  • 例如样例1中的两个数组：

    arr1 : 3 1 2 8 7 [5 9 4 6 0]

    arr2 : 1 2 3 7 8 [5 9 4 6 0]

    我们观察到 arr2 中前五个数都排好序了，那就直接跳过，从第六个数开始和原数组进行比较，发现完全相同，那就是插入排序

注意：

如果是 C++20 及以上可以用 make_heap 和 pop_heap 函数快速实现可控制排序次数的堆排序，否则就必须手搓 大根堆 进行原地排序，因为用 priority_queue 排序时不是原地排序，跟题目的序列会不一样

解题代码：

#include <iostream>
#include <vector>
#include <algorithm>

using std::cin;
using std::cout;

int main()
{
    int n;
    cin >> n;
    std::vector<int> arr1(n), arr2(n);
    for (int i = 0; i < n; i++) {cin >> arr1[i];}
    for (int i = 0; i < n; i++) {cin >> arr2[i];}

    bool isInsertion = true;
    int p = 1;
    while (p < n && arr2[p] >= arr2[p-1]) p++;
    for (int i = p; i < n; i++) {
        if (arr1[i] != arr2[i]) {
            isInsertion = false;
            break;
        }
    }

    auto print = [](const std::vector<int>& s) -> void {
        for (int i = 0; i < (int)s.size(); i++) {
            if (i) cout << ' ';
            cout << s[i];
        }
        cout << '\n';
    };

    if (isInsertion) {
        std::sort(arr2.begin(), arr2.begin() + std::min(p + 1, n));
        cout << "Insertion Sort\n";
        print(arr2);
    } else {
        std::ranges::make_heap(arr1);

        bool finish = false;
        for (int end = arr1.size(); end > 1; end--) {
            std::ranges::pop_heap(arr1.begin(), arr1.begin() + end);
            if (finish) break;
            if (arr1 == arr2) finish = true;
        }
        cout << "Heap Sort\n";
        print(arr1);
    }
    
    return 0;
}

5.排列还原

题目描述：

牛牛的作业簿上有一个长度为n的排列 $A[1\cdots n]$，这个排列包含了从 $1$ 到 $n$ 的 $n$ 个数，但是因为某种原因，其中有一些位置（不超过 $10$ 个）看不清了，但是牛牛记得这个排列的顺序对的数量是 $k$，顺序对是指满足 $i<j$ 且 $A[i]<A[j]$ 的对数。请帮助牛牛计算出符合要求的排列数目。输入 $n$,$k$ 与序列 $A$，返回可能的存在排列数目。

一看就是牛客上的题...

输入格式:

输入的第一行包含两个整数n和k($1\leq n \leq 100,1\leq k\leq n(n−1)/2$)，接下来的一行，包含 $n$ 个数字表示排列 $A$，其中等于0的项表示看不清的位置（不超过10个）。

输出格式:

输出一行表示合法排列的数目。

输入样例：

5 5
4 0 0 2 0

输出样例：

2

分析：

• 这题可以用 回溯全排序 的暴力做法去做，虽然时间复杂度来到了惊人的 $O(m! \cdot n^2)$，但是暴力做法仍然过了...

意味着下面给出的代码仍有较大优化空间

• 解释：全排序去枚举所有可能的组合然后去算每种组合的顺序对个数，符合题意就 ans++

注意：

PTA 的评测机貌似是 C++20 ，lambda函数 写 this auto&& self 会报错，可以用 auto&& self 或 std::function<> 的写法来代替，以实现自身递归调用

解题代码：

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

using std::cin;
using std::cout;

using u8 = uint8_t;

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    std::vector<int> a(n);
    std::vector<int> pos, miss;
    std::vector<u8> appear(n + 1, false);

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (a[i] == 0) pos.push_back(i);
        else appear[a[i]] = true;
    }

    for (int i = 1; i <= n; i++) {
        if (!appear[i]) miss.push_back(i);
    }

    auto countPair = [&]() -> int {
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (a[j] < a[i]) cnt++;
            }
        }
        return cnt;
    };

    int ans = 0;
    std::vector<u8> used(miss.size(), false);

    std::function<void(int)> dfs = [&](int step) {
        if (step == (int)pos.size()) {
            if (countPair() == k) ans++;
            return;
        }

        for (int i = 0; i < (int)miss.size(); i++) {
            if (used[i]) continue;

            used[i] = true;
            a[pos[step]] = miss[i];

            dfs(step + 1);

            used[i] = false;
            a[pos[step]] = 0;
        }
    };

    dfs(0);

    cout << ans;
    return 0;
}

8.棋盘覆盖

题目描述：

在一个 $2^k \times 2^k$ ($k$ 为正整数，$k\leq 10$，length= $2^k$)个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格（其坐标为a,b，分别代表行坐标号和列坐标号），以及有四种L型骨牌（如下图）。求用若干块这种L型骨牌实现除该特殊点棋盘的全覆盖。（本题要求采用分治算法做）

输入格式:

输入三个数，分别是a,b,length.

输出格式:

输出整个棋盘。其中特殊方格填为0，然后铺棋盘的顺序为：先铺四个子棋盘交界的部分，然后递归的对每个子棋盘按照左上，右上，右下，左下的顺时针顺序铺满棋盘。每一块骨牌中三个方格数字相同，按照顺序标号，即第一块骨牌全标为1，第二块骨牌全标为2，...，以此类推。输出的每个数占4个场宽，右对齐。

输入样例:

1 1 4

表示： 特殊格子为（1，1），棋盘有4行4列。

输出样例：

0   2   3   3
2   2   1   3
5   1   1   4
5   5   4   4

提示： 先铺三个1，再铺三个2，...，最后铺三个5（即先处理子问题交界的地方，再处理左上，右上，右下，左下的子问题）

分析：

• 将初始棋盘均分成四个象限，那只会有一个象限有特殊方格，此时在剩余三个象限去铺一个 L 型骨牌，此时每个象限都有一个特殊方格了(将骨牌覆盖的地方也视为特殊方格)

• 只看其中一个象限，将这个象限再分为四个象限，这四个象限依然只有一个象限有特殊方格，此时和前面的情况一直，直接在剩下三个象限铺 L 型，如此递归即可

• 递归出口：当递归到 $1\times 1$ 时不需要铺 L 型就退出，不建议在 $2 \times 2$ 时判断并退出，因为此时你要分 $4$ 种情况讨论(即按特殊方格所在的位置进行讨论)

说明：

这题限定了用递归做法，且递归顺序被固定，故答案唯一

由于分情况讨论的代码又臭又长，于是直接 copy 了 ChatGPT 的代码(记得 std::setw(4))

解题代码：

#include <iostream>
#include <iomanip>

using std::cin;
using std::cout;

const int MAXN = 1024;
int board[MAXN][MAXN];
int tile = 0;

void cover(int tr, int tc, int dr, int dc, int size) {
    if (size == 1) return;  // 1x1，不需要铺

    int t = ++tile;         // 当前这一块L型骨牌的编号
    int s = size / 2;       // 子棋盘边长

    // 1. 特殊格在左上
    if (dr < tr + s && dc < tc + s) {
        // 中央骨牌覆盖 右上、左下、右下
        board[tr + s - 1][tc + s] = t;
        board[tr + s][tc + s - 1] = t;
        board[tr + s][tc + s] = t;

        // 递归四个子棋盘：左上、右上、右下、左下
        cover(tr, tc, dr, dc, s);                               // 左上
        cover(tr, tc + s, tr + s - 1, tc + s, s);              // 右上
        cover(tr + s, tc + s, tr + s, tc + s, s);              // 右下
        cover(tr + s, tc, tr + s, tc + s - 1, s);              // 左下
    }
    // 2. 特殊格在右上
    else if (dr < tr + s && dc >= tc + s) {
        // 中央骨牌覆盖 左上、左下、右下
        board[tr + s - 1][tc + s - 1] = t;
        board[tr + s][tc + s - 1] = t;
        board[tr + s][tc + s] = t;

        cover(tr, tc, tr + s - 1, tc + s - 1, s);
        cover(tr, tc + s, dr, dc, s);
        cover(tr + s, tc + s, tr + s, tc + s, s);
        cover(tr + s, tc, tr + s, tc + s - 1, s);
    }
    // 3. 特殊格在左下
    else if (dr >= tr + s && dc < tc + s) {
        board[tr + s - 1][tc + s - 1] = t;
        board[tr + s - 1][tc + s] = t;
        board[tr + s][tc + s] = t;

        cover(tr, tc, tr + s - 1, tc + s - 1, s);
        cover(tr, tc + s, tr + s - 1, tc + s, s);
        cover(tr + s, tc + s, tr + s, tc + s, s);
        cover(tr + s, tc, dr, dc, s);
    }
    // 4. 特殊格在右下
    else {
        board[tr + s - 1][tc + s - 1] = t;
        board[tr + s - 1][tc + s] = t;
        board[tr + s][tc + s - 1] = t;

        cover(tr, tc, tr + s - 1, tc + s - 1, s);
        cover(tr, tc + s, tr + s - 1, tc + s, s);
        cover(tr + s, tc + s, dr, dc, s);
        cover(tr + s, tc, tr + s, tc + s - 1, s);
    }
}

int main() {
    int a, b, length;
    cin >> a >> b >> length;
    a--, b--;

    cover(0, 0, a, b, length);

    // 特殊格置0
    board[a][b] = 0;

    for (int i = 0; i < length; i++) {
        for (int j = 0; j < length; j++) {
            cout << std::setw(4) << board[i][j];
        }
        cout << '\n';
    }

    return 0;
}