PAT乙级1098题解：序列极值比较算法详解

1. 题目分析与解题思路

这道PAT乙级1098题考察的是对整数序列的基本操作和逻辑判断能力。题目给出了两个整数序列"上面"和"下面"，要求我们判断是否存在"上面"序列中的最小值比"下面"序列中的最大值大至少1的情况。

1.1 题目核心理解

题目给出的条件可以这样理解：

• 我们需要找到"上面"序列的最小值(min1)
• 找到"下面"序列的最大值(max1)
• 然后比较这两个值的关系

关键判断条件是：

• 如果min1 ≥ max1 + 1（即min1 - max1 ≥ 1），则输出"Yes"和差值
• 否则输出"No"和需要增加的最小值（即max1 - min1 + 1）

1.2 算法选择理由

选择这种解法的原因在于：

1. 时间复杂度最优：只需要O(n)的时间复杂度，因为我们只需要遍历两个数组各一次
2. 空间复杂度低：除了输入数组外，只使用了几个额外变量
3. 逻辑清晰：直接比较两个关键值就能得出结论

2. 代码实现详解

2.1 输入处理

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

int main() {
    int n;
    cin >> n;
    vector<int> shang(n);
    vector<int> xia(n);

这部分代码做了以下工作：

1. 包含常用头文件<bits/stdc++.h>
2. 使用标准命名空间std
3. 读取整数n表示序列长度
4. 创建两个vector容器shang和xia，大小都为n

注意：虽然<bits/stdc++.h>在竞赛中常用，但在实际工程中建议包含具体需要的头文件

2.2 寻找关键值

cpp复制int min1 = 1000, max1 = -1;
for(int i = 0; i < n; i ++) {
    cin >> shang[i];
    min1 = min(min1, shang[i]);
}
    
for(int i = 0; i < n; i ++) {
    cin >> xia[i];
    max1 = max(max1, xia[i]);
}

这部分代码的逻辑是：

1. 初始化mi