1-2025年计算机算法分析

必做题1 二维极大点问题 *

在一个二维平面上，如果有两个点(x1,y1)和(x2,y2)，有比较关系x1>x2且y1>y2，则称点(x1,y1)支配了(x2,y2)，(x1,y1)是极大点。 当比较关系修改为x1≥x2且y1≥y2时，支配关系会产生有趣的变化，下面考虑这种情况。对于给定n个点的集合，编程找出所有的极大点，按照x坐标由小到大，输出极大点的坐标。

输入格式:

输入包括两行，第一行是正整数n，表示是点的个数，第二行包含n个点的坐标，坐标值都是整数，x坐标和y坐标范围从0到1000，且输入数据中不存在坐标相同的点。

输出格式:

按x轴坐标最小到大的顺序输出所有极大点。 输出格式为:(x1,y1)(x2,y2)...(xk,yk)

输入样例:

5
1 2 2 2 3 1 2 3 1 4

输出样例:

(1,4)(2,3)(3,1)

解法一：分治策略

• 预处理排序所给点集按x值递增排序
• 二份递归处理，找到左右边界的可能极大点
• 右区间一定是极大点，因为上一层递归时已经过滤右区间里的左半部分的非极大点
• 同时处理左区间，找出右区间的最大y值去过滤左区间的极大点

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


//S预处理排序
vector<pair<int,int>> find_maxima(vector<pair<int, int>> S) {
    if (S.size() == 1) {
        return S;
    }

    int n = S.size();
    auto mid = S.begin() + n / 2;

    //根据x值从小到大排序，取中间分割
    vector<pair<int, int>> SL(S.begin(), mid);
    vector<pair<int, int>> SR(mid, S.end());

    //找到左右区间的可能极大点
    vector<pair<int, int>> sl_maxima = find_maxima(SL);
    vector<pair<int, int>> sr_maxima = find_maxima(SR);

    // 计算SR的极大点中的最大y值用于下面过滤左区间的极大点
    int max_y_sr = 0;
    for (const auto& p : sr_maxima) {
        if (p.second > max_y_sr) {
            max_y_sr = p.second;
        }
    }

    // 过滤SL的极大点，保留y大于max_y_sr的点
    vector<pair<int, int>> merged;
    for (const auto& p : sl_maxima) {
        if (p.second > max_y_sr) {
            merged.push_back(p);
        }
    }

    // 添加SR的所有极大点
    merged.insert(merged.end(), sr_maxima.begin(), sr_maxima.end());

    return merged;
}

int main()
{
    int n;
    cin >> n;
    vector<pair<int, int>> S(n), ans;
    for (int i = 0; i < n; i++)cin >> S[i].first >> S[i].second;
    sort(S.begin(), S.end());
    ans = find_maxima(S);

    for (const auto& k : ans)cout << "(" << k.first << "," << k.second << ")";
}

解法二：贪心策略

• 依旧预处理排序，按x从小到大排序，x相等时按y从小到大排序
• 然后逆序处理点集，即记录当前最大y值即当前点右边最大y值，如果当前点的y值大于最大y值，则为极大点，加入答案向量里，同时更新最大y值
• 最后答案逆序输出

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

using namespace std;

//按x从小到大排序，x相等时按y从小到大排序
bool cmp(pair<int, int> a, pair<int, int> b)
{
    return a.first < b.first || (a.first == b.first && a.second < b.second);
}

int main()
{
    int n;
    cin >> n;
    vector<pair<int, int>> points;
    vector<pair<int, int>> ans;
    for (int i = 0; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        points.push_back({ x,y });
    }
    sort(points.begin(), points.end(), cmp);

    //记录当前点右侧最大y值
    int pre_y = INT_MIN;
    for (auto it = points.rbegin(); it != points.rend(); it++)
    {
        //找到极大点并更新pre_y
        if (it->second > pre_y)
        {
            ans.push_back(*it);
            pre_y = it->second;
        }
    }

    //逆序输出
    for (int i = ans.size() - 1; i >= 0; i--)
    {
        cout << "(" << ans[i].first << "," << ans[i].second << ")";
    }
    return 0;
}

必做题2 带有期限的作业调度问题 *

带有期限的作业调度问题要解决的是操作系统中单机、无资源约束且每个作业可在等量时间内完成的作业调度问题，形式化描述为：

1. 只能在一台机器上处理 n 个作业，每个作业 i=1,...,n 均可在单位时间内完成。

2. 每个作业 i 都有一个期限值 d**i>0，（ d**i 是整数）。

3. 当且仅当作业 i 在它的截止期限前被完成时获得 p**i>0 的效益；问题的可行解是这 n 个作业的一个子集合。集合中的每个作业都能在各自的截止期限之前完成，产生一个作业效益之和 ∑p**i 。具有最大效益值的可行解就是最优解。

   输入格式:

   第一行为一个正整数n，表示作业的个数；

   接下来的 n 行，每行两个正整数（中间用空格隔开），表示每个作业 i 的截止

   期限 d**i 和按期完成产生的效益p**i。

   输出格式:

   一行一个整数，给出最优解的效益值。

   输入样例1:

4
1 20
2 15
2 100
1 10

输出样例1:

120

输入样例2:

6
2 25
3 20
3 15
2 10
4 1
4 5

输出样例2:

65

数据范围

d**i≤n≤10^6,p**i≤10^9

[!important]

根据效益值的数值范围需要用到long long数据类型

解法一：基于插入排序

• 预处理排序，按利润递减排序
• 按时间片从前往后安排，当处理新的作业，尽量往前安排，即找到已经安排的作业中第一个截止时间小于当前作业期限的，并且避免当前作业期限中没有最拖延的作业（即无法继续延后的作业D[J[r]] != r）
• 找到插入位置并且当前位置作业可行(D[i]>r)
• 依次后移已经调度的作业，然后加入当前处理作业

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

using namespace std;

void JS(std::vector<int>& D, std::vector<int>& J, int n, int& k) {
    D[0] = 0;
    J[0] = 0;
    k = 1;
    J[1] = 1;
    //处理第i个作业
    for (int i = 2; i <= n; ++i) {
        int r = k;
        //找到插入的前驱r
        while (D[J[r]] > D[i] && D[J[r]] != r) {
            --r;
        }
        //表示找到了插入位置r
        if (D[J[r]] <= D[i] && D[i] > r) {
            //实现作业r+1到作业k依次往后移动一个位置
            for (int l = k; l >= r + 1; --l) {
                J[l + 1] = J[l];
            }
            //插入
            J[r + 1] = i;
            ++k;
        }
    }
}

int main()
{
    int n;
    cin >> n;
    vector<pair<int, int>> job;
    vector<int> j(n+1);
    for (int i = 0; i < n; i++) {
        int d, p;
        cin >> d >> p;
        job.push_back({ p,d });
    }
    sort(job.begin(), job.end(), greater<pair<int, int>>());
    vector<int> D(1);
    for (const auto k : job)
    {
        D.push_back(k.second);
    }
    int k;
    JS(D, j, n, k);
    long long ans = 0;
    for (int i = 1; i <= k; i++)
    {
        ans += job[j[i] - 1].first;
    }
    cout << ans;
}

• 考虑二分查找优化寻找插入位置，但是因为遍历时同时需要判断是否有无法延后的作业，所以无法使用二分查找优化
• 下面为尝试的代码

void JS(vector<int>& D, vector<int>& J, int n, int& k) {
    D[0] = 0;
    J[0] = 0;
    k = 1;
    J[1] = 1;

    for (int i = 2; i <= n; ++i) {
        int left = 1, right = k;
        int r = 0;

        // 二分查找满足 D[J[mid]] <= D[i] 或 D[J[mid]] == mid 的最大r
        while (left <= right) {
            int mid = (left + right) / 2;
            if (D[J[mid]] <= D[i] || D[J[mid]] == mid) {
                r = mid;          // 当前mid满足条件，记录位置
                left = mid + 1;   // 继续向右寻找更大的r
            } else {
                right = mid - 1;  // 不满足条件，向左调整
            }
        }

        // 检查是否满足插入条件
        if (D[i] > r) {
            // 后移作业腾出位置r+1
            for (int l = k; l >= r + 1; --l) {
                J[l + 1] = J[l];
            }
            J[r + 1] = i;
            ++k;
        }
    }
}

解法二：基于并查集的算法

• 预处理排序作业集合按利润递减排序
• 同时利用压缩路径减少查找根时间
• 这种算法可以理解为上一算法的相反，上一算法是尽量往前排
• 而这一算法则是尽量往后排序，能拖延就拖延
• 并且可以可以理解每一个集合的根就是当前空余时间片

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

using namespace std;


int find_root(vector<int>& p, int x) {
    return p[x] == x ? x : p[x] = find_root(p, p[x]);

}

int main(){
    int n;
    cin >> n;
    vector<pair<int, int>> jobs; // 存储为(p, d)对

    for (int i = 0; i < n; ++i) {
        int d, p;
        cin >> d >> p;
        jobs.push_back({ p, d });
    }

    // 按效益降序排序
    sort(jobs.begin(), jobs.end(), greater<pair<int, int>>());

    vector<int> parent(n + 1);
    for (int i = 0; i <= n; i++)parent[i] = i;
    long long ans = 0;

    for (const auto& job : jobs) {
        int p = job.first;
        int d = job.second;
        int adjusted_d = min(d, n); // 调整期限不超过n
        int r = find_root(parent,adjusted_d);

        if (r > 0) {
            ans += p;
            parent[r] = find_root(parent,r - 1); // 合并到前一个时间点
        }
    }

    cout << ans << endl;
    return 0;
}

选做题1 基于递归算法解决0/1背包问题

背包可容纳物品的最大质量为m，现有n件物品，质量分别为m1,m2,...,m**n,，其中m**i均为正整数。请编写程序，从物品n到物品1逐个考虑，在n件物品中挑选若干件，使放入背包的物品质量之和正好为m。

输入格式:

输入为2行。第一行为两个正整数m,n，表示背包可容纳物品的质量和物品数量，第二行为n个整数，表示物品的重量列表。

输出格式:

输出为1行空格间隔的整数，表示放入背包的各物品重量。若无解，则输出0。

输入样例1:

5 4
1 6 2 3

输出样例1:

2 3

输入样例2:

5 4
3 4 4 3

输出样例2:

0

[!warning]

注意：因为题目没有说方案唯一所以为了输出对应答案的方案所以不要改变处理物品的次序，即不要排序

本体由于老师问题，导致题目不严谨，只能采用从后向前的顺序才能解出来，从前到后顺序会错 题目没说明白如果多个答案情况，是怎么取舍问题，所以暂时不理会

解法一：暴力递归

首先明白这道题不同于一般的0/1背包问题，不是求最大收益的装法而是求一个刚好装满的方案

• 这样子就有可以利用递归解决问题

  对于物品i以及剩余空间w

  1. 当空间小于零或者没有物品分配时无法找到合理方案返回false
  2. 当剩余空间刚好等于物品重量则成功找到方案返回true
  3. 紧接着则考虑是否装入当前物品分为两个路径
     1. 装入当前物品
     2. 不装当前物品
  4. 根据下一层递归判断是否装入当前物品并输出结果

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

// 递归函数：判断是否可以从数组中找到若干个数，使得它们的和等于目标值w
bool find(const vector<int>& obj, int i, int w) {
    // 如果目标和w小于0，或者索引i小于0，返回false
    if (w < 0 || i < 0) return false;

    // 如果目标和w等于当前元素obj[i]，输出该元素并返回true
    if (w == obj[i]) { 
        cout << obj[i]; 
        return true; 
    }

    // 尝试包含当前元素obj[i]，递归调用find函数
    if (find(obj, i - 1, w - obj[i])) {
        cout << " " << obj[i]; // 输出当前元素
        return true;
    }

    // 尝试不包含当前元素obj[i]，递归调用find函数
    if (find(obj, i - 1, w)) return true;

    // 如果两种情况都无法找到满足条件的组合，返回false
    return false;
}

int main() {
    int m, n; // m为目标和，n为数组大小
    cin >> m >> n; // 输入目标和和数组大小
    vector<int> obj(n); // 创建数组
    for (int i = 0; i < n; i++) {
        cin >> obj[i]; // 输入数组元素
    }

    // 调用find函数，从数组最后一个元素开始，目标和为m
    if (!find(obj, n - 1, m)) cout << 0; // 如果未找到，输出0
    cout << endl; // 输出换行
    return 0;
}

解法二：记忆化搜索

在递归的基础上可以发现有重复的子问题所以可以通过备忘录记录子问题的解

vector<vector<int>>& memo,memo[i][w]，对于物品i剩余w空间时能否装满

根据剩余空间相同对于同一物品的装载应该有相同的解法，所以通过记忆化搜索，记录子问题的解避子问题重复计算

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

// 递归函数：使用记忆化优化
int find(const vector<int>& obj, int i, int w, vector<vector<int>>& memo) {
    // 如果目标和w小于0，或者索引i小于0，返回false
    if (w < 0 || i < 0) return false;

    // 如果目标和w等于当前元素obj[i]，输出该元素并返回true
    if (w == obj[i]) {
        cout << obj[i];
        return memo[i][w]=1;
    }

    // 如果已经计算过这个子问题，直接返回结果
    if (memo[i][w] != -1) return memo[i][w];

    // 尝试包含当前元素obj[i]，递归调用find函数
    if (find(obj, i - 1, w - obj[i], memo)) {
        cout << " " << obj[i]; // 输出当前元素
        return memo[i][w]=1; // 记录结果为true
    }

    // 尝试不包含当前元素obj[i]，递归调用find函数
    if (find(obj, i - 1, w, memo)) {
        return memo[i][w]=1; // 记录结果为true
    }

    // 如果两种情况都无法找到满足条件的组合，记录结果为false并返回
     return memo[i][w] = 0;
}

int main() {
    int m, n; // m为目标和，n为数组大小
    cin >> m >> n; // 输入目标和和数组大小
    vector<int> obj(n); // 创建数组
    for (int i = 0; i < n; i++) {
        cin >> obj[i]; // 输入数组元素
    }

    // 初始化记忆化数组，-1表示未计算过
    vector<vector<int>> memo(n, vector<int>(m + 1, -1));

    // 调用find函数，从数组最后一个元素开始，目标和为m
    if (!find(obj, n - 1, m, memo)) cout << 0; // 如果未找到，输出0
    cout << endl; // 输出换行
    return 0;
}

解法三：动态规划

• 可以将记忆化搜索理解为自顶而下的动态规划，所以肯定也可以自底而上进行动态规划，可以从前往后处理物品
• dp[i][j]表示前i个元素是否可以组成和为j的子集，注意为前i个元素，所以dp[1][0]，表示的是物品0
• 边界条件：：dp[i][0] = true，和为0的情况总是可以实现的即不选任何元素
• 动态转移方程分为两个情况
• j>=obj[i-1],dp[i][j] = dp[i - 1][j] || dp[i - 1][j - obj[i - 1]];
• j<obj[i-1],dp[i][j] = dp[i - 1][j];
• 最后通过dp[n][m]可以判断是否存在合理方案

[!important]

因为需要构造最优解所以进行回溯状态获得答案

从动态规划表的最后一个元素开始回溯，如果如果当前目标和大于等于当前元素，并且去掉当前元素后仍然可以组成目标和，即当前物品为方案中的物品，同时减少目标和继续回溯

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

// 函数：判断是否可以找到一个子集，使得其和为m
bool subsetSum(vector<int>& obj, int m) {
    int n = obj.size();
    // 创建动态规划表，dp[i][j]表示前i个元素是否可以组成和为j的子集
    vector<vector<bool>> dp(n + 1, vector<bool>(m + 1, false));

    // 初始化：dp[i][0] = true，表示和为0的情况总是可以实现的（不选任何元素）
    for (int i = 0; i <= n; ++i) {
        dp[i][0] = true;
    }

    // 动态规划填表
    for (int i = 1; i <= n; ++i) { // 遍历每个元素
        for (int j = 1; j <= m; ++j) { // 遍历每个可能的目标和
            // 如果当前目标和大于等于当前元素的值
            if (j >= obj[i - 1]) {
                // 有两种选择：不选当前元素，或者选当前元素
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - obj[i - 1]];
            } else {
                // 如果目标和小于当前元素的值，只能不选当前元素
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    // 如果dp[n][m]为true，说明可以找到满足条件的组合
    if (!dp[n][m]) {
        return false;
    }

    // 回溯找到具体的组合
    vector<int> result;
    int i = n, j = m;
    while (i > 0 && j > 0) { // 从动态规划表的最后一个元素开始回溯
        // 如果当前目标和大于等于当前元素，并且去掉当前元素后仍然可以组成目标和，即当前物品为方案中的物品
        if (j >= obj[i - 1] && dp[i - 1][j - obj[i - 1]]) {
            result.push_back(obj[i - 1]); // 将当前元素加入结果
            j -= obj[i - 1]; // 更新目标和
        }
        i--; // 移动到上一个元素
    }

    // 输出结果
    for (int i = result.size() - 1; i >= 0; --i) { // 逆序输出结果
        cout << result[i] << (i > 0 ? " " : "");
    }
    return true;
}

int main() {
    int m, n;
    cin >> m >> n; // 输入目标和m和数组大小n
    vector<int> obj(n);
    for (int i = 0; i < n; i++) {
        cin >> obj[i]; // 输入数组元素
    }

    // 调用subsetSum函数，判断是否存在满足条件的子集
    if (!subsetSum(obj, m)) {
        cout << "0" << endl; // 如果不存在，输出"No solution"
    } else {
        cout << endl; // 如果存在，输出换行
    }
    return 0;
}

选做题2 地牢逃生

用一个 n×n 的矩阵表示一座地牢，矩阵中第 i 行第 j 列的方格的值表示位置 (i,j) 的地势高度 h(i,j)。 时间 T=0 的时刻地牢开始下雨，当时间 T=t 时，地牢任意位置的水位都等于t 。任意时刻可以从当前位置游向上下左右四周相邻的任意一个位置，但是游动的前提是：此时水位必须淹没这个位置和其相邻位置，即如果在 T=t 时想从 (i,j) 位置移动到 (i,j+1) 位置，需要满足t≥h(i,j),t≥h(i,j+1) 。假定在方格内部游动不耗时。时间 T 的取值是正整数。 求：从 (1,1) 位置出发，最少耗时多久可以到达 (n,n) 。

输入格式

第一行一个整数 n 。 接下来 n 行，每行 n 个整数，代表 h(i,j) 。

输出格式

输出一个整数，表示最少耗时。

输入样例

2
0 2
1 3

输出样例

3

样例说明

时间 T=0 时，位于坐标方格的位置为 (1,1)。此时不能游向任意方向，因为相邻方向平台的高度都大于当前时间为 0 时的水位。 时间 T=1 时，可以游到 (2,1)；时间 T=2 时，可以游到 (2,1)和(1,2)，时间 T=3 时，才可以游到 (2,2) 。 因为此时的水位是 3，坐标方格中的平台没有比水位 3 更高的，所以可以游向坐标方格中的任意位置。

数据范围

n≤1000,0≤h(i,j)≤10^6

[!important]

注意：该问题的数据有缺陷仅仅考虑从左边和上边的移动但是题目说明可以四周移动，数据却没有考虑这种情况即第一行的格子可以从下面到达或者第一列的格子可以从右边到达，显然下面两种解法都没有考虑到，数据导致下面记忆化搜索和动态规划可以AC，但是这道题778. 水位上升的泳池中游泳不能利用下述两种写法，必须利用解法三

解法一：记忆化搜索

• 初始化：dp[0][0]=h[0][0];起点 (0,0) 到达自身的最短时间就是该位置的地势高度
• if(i==0)return dp[i][j]=max(h[i][j],minT(i,j-1,h));
• if(j==0)return dp[i][j]=max(h[i][j],minT(i-1,j,h));
• 起点 (0,0) 到达 (i,0) 或 (0,j) 的最短时间,等于当前位置的地势高度和上(左)一个位置的最短时间的最大值。
• 其他位置：dp[i][j] = max(h[i][j], min(minT(i-1,j,h), minT(i,j-1,h)));从起点 (0,0) 到达 (i,j) 的最短时间,等于当前位置的地势高度和上一个位置的最短时间的最大值

#include<iostream>
#include<queue>
#include<unordered_map>
#include<algorithm>
#include<climits>
#include<vector>
using namespace std;

vector<vector<int>> dp;

int minT(int i, int j, const vector<vector<int>>& h)
{
    if (dp[i][j] != -1)return dp[i][j];

    if(i==0)return dp[i][j]=max(h[i][j],minT(i,j-1,h));
    if(j==0)return dp[i][j]=max(h[i][j],minT(i-1,j,h));

    return dp[i][j] = max(h[i][j], min(minT(i-1,j,h), minT(i,j-1,h)));

}

int main()
{
    int n;
    cin >> n;
    vector<vector<int>> h(n, vector<int>(n));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> h[i][j];
    dp.resize(n, vector<int>(n, -1));
    dp[0][0]=h[0][0];
    cout << minT(n - 1, n - 1, h);
    return 0;
}

解法二：动态规划

根据记忆化搜索可以退出自底而上的动态规划

状态转移方程

• 初始化：dp[0][0]=h[0][0];
• 边界if(i==0)return dp[i][j]=max(h[i][j],dp[i][j-1]);
• 边界if(j==0)return dp[i][j]=max(h[i][j],dp[i-1][j]);
• 基本情况dp[i][j] = max(h[i][j], min(dp[i-1][j],dp[i][j-1]));

#include<iostream>
#include<queue>
#include<unordered_map>
#include<algorithm>
#include<climits>
#include<vector>
using namespace std;

int minT(int i, int j, const vector<vector<int>>& h)
{
    int n=h.size();
    //备忘录
    vector<vector<int>> dp;
    dp.resize(n, vector<int>(n, -1));
    //初始化
    dp[0][0]=h[0][0];
    //边界
    for(int i=1;i<n;i++)
    {
        dp[i][0]=max(h[i][0],dp[i-1][0]);
        dp[0][i]=max(h[0][i],dp[0][i-1]);
    }
    //遍历
    for(int i=1;i<n;i++)
        for(int j=1;j<n;j++)
            dp[i][j]=max(h[i][j],min(dp[i-1][j],dp[i][j-1]));

    return dp[n-1][n-1];
}

int main()
{
    int n;
    cin >> n;
    if(n<=0)return 0;
    vector<vector<int>> h(n, vector<int>(n));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> h[i][j];
    cout << minT(n - 1, n - 1, h);
    return 0;
}

• 优化，因为当前状态(i,j)只和(i,j-1)和(i-1,j)有关
• 所以采用滚动数组优化空间复杂度

#include<iostream>
#include<queue>
#include<unordered_map>
#include<algorithm>
#include<climits>
#include<vector>
using namespace std;

int minT(int i, int j, const vector<vector<int>>& h)
{
    int n=h.size();
    //备忘录
    vector<vector<int>> dp;
    dp.resize(2, vector<int>(n, -1));
    //初始化
    dp[0][0]=h[0][0];
    //边界
    for(int i=1;i<n;i++)
    {
        dp[0][i]=max(h[0][i],dp[0][i-1]);
    }

    int current=0;//所要处理的数组
    //遍历
    for(int i=1;i<n;i++)
    {
        current=current==1?0:1;
        for(int j=0;j<n;j++)
        {
            int pre_i=current==1?0:1;
            if(j==0)dp[current][j]=max(h[i][j],dp[pre_i][j]);
            else dp[current][j]=max(h[i][j],min(dp[pre_i][j],dp[current][j-1]));
        }   
    }
    return dp[current][n-1];
}

int main()
{
    int n;
    cin >> n;
    if(n<=0)return 0;
    vector<vector<int>> h(n, vector<int>(n));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> h[i][j];
    cout << minT(n - 1, n - 1, h);
    return 0;
}

• 还可以优化为一维数组，同时记录上一个维度对应的状态即pre_dp=dp[i-1][j]用于dp[i][j] = max(h[i][j], min(minT(i-1,j,h), minT(i,j-1,h)))

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

using namespace std;



int minT(int i, int j, const vector<vector<int>>& h)
{
    int n=h.size();
    //备忘录
    vector<int> dp(n,-1);

    //初始化
    dp[0]=h[0][0];
    //边界
    for(int i=1;i<n;i++)
    {
        dp[i]=max(h[0][i],dp[i-1]);
    }

    //遍历
    for(int i=1;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            int pre_j=dp[j]; 
            if(j==0)dp[j]=max(h[i][j],pre_j);
            else dp[j]=max(h[i][j],min(dp[j-1],pre_j));
        }   
    }
    return dp[n-1];
}

int main()
{
    int n;
    cin >> n;
    if(n<=0)return 0;
    vector<vector<int>> h(n, vector<int>(n));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> h[i][j];
    cout << minT(n - 1, n - 1, h);
    return 0;
}

解法三：二分答案 + BFS

• 即通过最大高度获取中间值，假设该值可以连通终点和起点进行搜索，如果可以再次二分取更小的时刻进行尝试，相反则取更大的时刻进行尝试

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;          // 最大边长
const int dx[] = {1, -1, 0, 0}; // 四联通：下、上、右、左
const int dy[] = {0, 0, 1, -1};

int n, h[MAXN][MAXN];           // 读入的地牢高度
bool vis[MAXN][MAXN];           // BFS 时判重

/* ---------- 二分 check 函数 ---------- */
// 在水位 = t 时，能否从 (1,1) 四向游到 (n,n)
bool check(int t) {
    // 起点或终点本身就被淹没不了，直接失败
    if (h[1][1] > t || h[n][n] > t) return false;

    memset(vis, 0, sizeof(vis));            // 多组数据清空标记
    queue<pair<int, int>> q;
    q.emplace(1, 1);
    vis[1][1] = true;

    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        if (x == n && y == n) return true;  // 已到达终点
        for (int d = 0; d < 4; ++d) {
            int nx = x + dx[d], ny = y + dy[d];
            // 出界、已访问、目标平台比水位高 → 跳过
            if (nx < 1 || nx > n || ny < 1 || ny > n) continue;
            if (vis[nx][ny] || h[nx][ny] > t) continue;
            vis[nx][ny] = true;
            q.emplace(nx, ny);
        }
    }
    return false;   // BFS 结束仍未到达
}

/* ---------- 主程序 ---------- */
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    int mx = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) {
            cin >> h[i][j];
            mx = max(mx, h[i][j]);  // 记录最大高度作为二分上界
        }

    // 二分答案：最小能让 (1,1) 游到 (n,n) 的水位 t
    int lo = 0, hi = mx, ans = mx;
    while (lo <= hi) {
        int mid = (lo + hi) >> 1;
        if (check(mid)) {   // mid 时刻能到，尝试更小
            ans = mid;
            hi = mid - 1;
        } else {            // mid 时刻到不了，需要更大
            lo = mid + 1;
        }
    }
    cout << ans << '\n';
    return 0;
}

解法四：并查集

• 将问题转换为什么时刻可以将终点和起点连通起来，即归为一个集合

• 从小到大依次考虑 threshold，那么每次考虑一个新值时，只需要在上一个阶段的图中，添加几条新边而已，而无需重新构建整张图。

• 具体而言，我们维护每个高度值对应的方块位置，当考虑 threshold 时，我们首先找出对应的方块位置，然后对于每个与之相邻的方块，如果相邻的方块的高度值不超过 threshold，就在两个方块之间连接一条边。当所有相邻方块都被考虑完毕时，再判断起点和终点是否连通

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;              // 最大边长
int grid[MAXN][MAXN];               // 存地牢高度（0-based）

/* --------------- 并查集 --------------- */
int fa[MAXN * MAXN];                // 父数组，下标 = i*n+j
int find(int x) {                   // 路径压缩
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y) {          // 按秩合并（这里没写秩，够用）
    x = find(x), y = find(y);
    if (x != y) fa[x] = y;
}

/* --------------- 核心：按水位从小到大合并，直到起点终点连通 --------------- */
int solve(int n) {
    int total = n * n;              // 总格子数
    for (int i = 0; i < total; ++i) fa[i] = i; // 并查集初始化

    /* 1. 把所有格子按高度升序排序，方便“模拟下雨” */
    vector<pair<int, int>> cells;   // first=高度，second=线性坐标
    cells.reserve(total);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            cells.emplace_back(grid[i][j], i * n + j);
    sort(cells.begin(), cells.end());

    /* 2. 四联通方向数组 */
    const int dx[] = {0, 0, 1, -1};
    const int dy[] = {1, -1, 0, 0};

    /* 3. 按水位从小到大处理每个格子 */
    for (auto &p : cells) {
        int threshold = p.first;    // 当前水位（下雨到 t 时刻）
        int pos       = p.second;   // 当前格子线性下标
        int i = pos / n, j = pos % n;

        /* 4. 把四周“已露出”且高度 <= threshold 的格子与当前格合并 */
        for (int d = 0; d < 4; ++d) {
            int ni = i + dx[d], nj = j + dy[d];
            if (ni < 0 || ni >= n || nj < 0 || nj >= n) continue;
            if (grid[ni][nj] <= threshold) merge(pos, ni * n + nj);
        }

        /* 5. 一旦起点 (0,0) 与终点 (n-1,n-1) 连通，当前水位即为答案 */
        if (find(0) == find(total - 1)) return threshold;
    }
    return -1; // 理论上不会执行
}

/* --------------- ACM 风格主程序 --------------- */
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            cin >> grid[i][j];

    cout << solve(n) << '\n';
    return 0;
}

解法五：优先队列

• “每次从已访问区域向外扩展高度最小的邻格，保证第一次到达终点时所用的最大高度就是答案。”

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
int grid[MAXN][MAXN];
bool vis[MAXN][MAXN];

/* --------------- 小根堆元素 --------------- */
struct Node {
    int i, j, maxH;
    Node(int _i, int _j, int _maxH): i(_i), j(_j), maxH(_maxH) {}
    bool operator<(const Node& rhs) const {
        return maxH > rhs.maxH;   // 小根堆
    }
};

/* --------------- 主逻辑 --------------- */
int solve(int n) {
    memset(vis, 0, sizeof(vis));
    priority_queue<Node> pq;
    pq.push(Node(0, 0, grid[0][0]));

    const int dx[] = {0, 0, 1, -1};
    const int dy[] = {1, -1, 0, 0};

    while (!pq.empty()) {
        Node cur = pq.top(); pq.pop();
        int i = cur.i, j = cur.j;
        if (vis[i][j]) continue;
        vis[i][j] = true;

        /* 第一次到终点即为答案 */
        if (i == n - 1 && j == n - 1) return cur.maxH;

        for (int d = 0; d < 4; ++d) {
            int ni = i + dx[d], nj = j + dy[d];
            if (ni < 0 || ni >= n || nj < 0 || nj >= n) continue;
            if (!vis[ni][nj]) {
                pq.push(Node(ni, nj, max(cur.maxH, grid[ni][nj])));
            }
        }
    }
    return -1; // 不会执行
}

/* --------------- ACM 入口 --------------- */
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;  cin >> n;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            cin >> grid[i][j];

    cout << solve(n) << '\n';
    return 0;
}

选做题3 分糖果问题

已知一些孩子n（1≤n≤20000）和一些糖果m（1≤m≤20000），每个孩子有需求因子g，每个糖果有大小s，当某个糖果的大小s>=某个孩子的需求因子g时，代表该糖果可以满足该孩子。求使用这些糖果，最多能满足多少个孩子（注意，某个孩子最多只能用1个糖果满足）。

输入格式:

第 1 行两个整数 m 和 n, 表示糖果数和孩子数。

第2行m个整数，表示各糖果的大小。

第3行n个整数，表示孩子的需求因子。

输出格式:

一个整数，表示能够满足要求的孩子数。

输入样例1:

1 1
2
3

输出样例1:

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

0

输入样例2:

1 1
3
2

输出样例2:

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

1

解法一：贪心算法

类似详见分发饼干

• 预处理需求数组和糖果数组，按递增次序排序
• 然后从后往前遍历先用大糖果满足大胃口

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

using namespace std;

int findContentChildren(vector<int>& g, vector<int>& s) {
    sort(g.begin(), g.end());
    sort(s.begin(), s.end());
    int index = s.size() - 1; // 糖果数组的下标
    int result = 0;
    for (int i = g.size() - 1; i >= 0; i--) { // 遍历胃口
        if (index >= 0 && s[index] >= g[i]) { // 遍历糖果
            result++;
            index--;
        }
    }
    return result;
}

int main()
{
    int m, n;
    cin >> m >> n;
    vector<int> c(n);
    vector<int> t(m);
    for (int i = 0; i < m; i++)cin >> t[i];
    for (int i = 0; i < n; i++)cin >> c[i];
    cout << findContentChildren(c, t);

}

• 同理可以从前往后遍历，先用小糖果满足小胃口，及尽量满足当前孩子需求

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());
        int index = 0;
        for(int i = 0; i < s.size(); i++) { // 饼干
            if(index < g.size() && g[index] <= s[i]){ // 胃口
                index++;
            }
        }
        return index;
    }
};

解法二：排序 + 双指针 + 贪心

1. 从贪心的角度考虑，应该按照孩子的胃口从小到大的顺序依次满足每个孩子，且对于每个孩子，应该选择可以满足这个孩子的胃口且尺寸最小的饼干
2. 其实类似于解法一，不过这里在遍历数组循环里通过while循环找到满足这个孩子的胃口且尺寸最小的饼干，避免每次判断

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int m = g.size(), n = s.size();
        int count = 0;
        for (int i = 0, j = 0; i < m && j < n; i++, j++) {
            while (j < n && g[i] > s[j]) {
                j++;
            }
            if (j < n) {
                count++;
            }
        }
        return count;
    }
};

选做题4 最大整数问题

设有 n 个正整数（n≤20），将它们连接成一排，组成一个最大的多位整数。 例如，n=3 时，3个整数13，312，343 连接成的最大整数为34331213；又如n=4 时，4 个整数 7，13，4，246 连接成的最大整数为7424613。

输入格式:

第一行是一个自然数 n。 第二行是n 个正整数。

输出格式:

连接成的多位最大整数。

输入样例1:

3
13 312 343

输出样例1:

34331213

输入样例2:

4
7  13  4  246

输出样例2:

7424613

解法一：贪心策略

[!important]

这道题巧妙的地方在于全程利用字符串进行解题，而非将每个数看作数字进行解题

因为字符串对应的大小即字典序也是对应数值的大小

• 重点

[!tip]

bool cmp(string a, string b)
{
    return a + b > b + a;
}

• 利用这个比较函数可以判断两个相邻字符串最大顺序

• 注意特殊情况，即所有数都是0时，可能最后答案将会是一串0不合理，需要特殊判断首字符是否为0

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

using namespace std;

bool cmp(string a, string b)
{
    return a + b > b + a;
}

int main()
{
    int n;
    cin >> n;
    if (n == 0)return 0;
    vector<string> nums(n);
    for (int i = 0; i < n; i++)cin >> nums[i];
    sort(nums.begin(), nums.end(), cmp);
    if (nums[0][0] == '0')cout << 0;
    else
    {
        for (const auto k : nums)cout << k;
    }
    return 0;
}