1098 岩洞施工 – PAT乙级真题

要将一条直径至少为 1 个单位的长管道水平送入地形复杂的岩洞中，究竟是否可能？下面的两幅图分别给出了岩洞的剖面图，深蓝色的折线勾勒出岩洞顶部和底部的轮廓。图 1 是有可能的，绿色部分显示直径为 1 的管道可以送入。图 2 就不可能，除非把顶部或底部的突出部分削掉 1 个单位的高度。

本题就请你编写程序，判断给定的岩洞中是否可以施工。

输入格式：

输入在第一行给出一个不超过 100 的正整数 N，即横向采样的点数。随后两行数据，从左到右顺次给出采样点的纵坐标：第 1 行是岩洞顶部的采样点，第 2 行是岩洞底部的采样点。这里假设坐标原点在左下角，每个纵坐标为不超过 1000 的非负整数。同行数字间以空格分隔。

题目保证输入数据是合理的，即岩洞底部的轮廓线不会与顶部轮廓线交叉。

输出格式：

如果可以直接施工，则在一行中输出 Yes 和可以送入的管道的最大直径；如果不行，则输出 No 和至少需要削掉的高度。答案和数字间以 1 个空格分隔。

输入样例 1：

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

输出样例 1：

Yes 1

输入样例 2：

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

输出样例 2：

No 1

分析：找到上壁的最低点minA、下壁的最高点maxB，如果minA<=minB，则输出No，需要削掉的高度为maxB-minA+1；否则输出Yes，管道的最大直径为minA-maxB~

#include <bits/stdc++.h>
using namespace std;
int n, a, b, minA = 2000, maxB;
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a;
        minA = min(a, minA);
    }
    for (int i = 0; i < n; i++) {
        cin >> b;
        maxB = max(b, maxB);
    }
    if (minA <= maxB) 
        cout << "No " << maxB - minA + 1;
    else 
        cout << "Yes " << minA - maxB;
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

int n, a, b, minA = 2000, maxB;

int main() {

cin >> n;

for (int i = 0; i < n; i++) {

cin >> a;

minA = min(a, minA);

}

for (int i = 0; i < n; i++) {

cin >> b;

maxB = max(b, maxB);

}

if (minA <= maxB)

cout << "No " << maxB - minA + 1;

else

cout << "Yes " << minA - maxB;

return 0;

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版