PTA B1098 岩洞施工 C++/Python3
题目描述
要将一条直径至少为 1 个单位的长管道水平送入地形复杂的岩洞中,究竟是否可能?下面的两幅图分别给出了岩洞的剖面图,深蓝色的折线勾勒出岩洞顶部和底部的轮廓。图 1 是有可能的,绿色部分显示直径为 1 的管道可以送入。图 2 就不可能,除非把顶部或底部的突出部分削掉 1 个单位的高度。
本题就请你编写程序,判断给定的岩洞中是否可以施工。
输入格式
输入在第一行给出一个不超过 100 的正整数 N,即横向采样的点数。随后两行数据,从左到右顺次给出采样点的纵坐标:第 1 行是岩洞顶部的采样点,第 2 行是岩洞底部的采样点。这里假设坐标原点在左下角,每个纵坐标为不超过 1000 的非负整数。同行数字间以空格分隔。
题目保证输入数据是合理的,即岩洞底部的轮廓线不会与顶部轮廓线交叉。
输出格式
如果可以直接施工,则在一行中输出 Yes 和可以送入的管道的最大直径;如果不行,则输出 No 和至少需要削掉的高度。答案和数字间以 1 个空格分隔。
样例 #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
样例输入 #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
C++
#include <bits/stdc++.h>
using namespace std;
int n;
int low=21e6,high;
signed main() {
cin>>n;
int temp;
//找上岩壁的最低点和下岩壁的最高点
for(int i=0; i<n; ++i) {
cin>>temp;
low=min(low,temp);
}
for(int i=0; i<n; ++i) {
cin>>temp;
high=max(high,temp);
}
//如果上岩壁最低点小于等于下岩壁最高点,说明管道不能通过
//如果不能通过,求差值+1,表示要挖的高度
//反之求差值,表示空隙高度
if(low<=high) {
cout<<"No"<<" "<<high-low+1;
} else cout<<"Yes"<<" "<<low-high;
return 0;
}
Python3/Pypy3
n = int(input())
lst1 = list(map(int, input().split()))
lst2 = list(map(int, input().split()))
low = 21e6
high = 0
for i in lst1:
low = min(i, low)
for i in lst2:
high = max(i, high)
print("No " + str(high - low + 1) if low <= high else "Yes " + str(low - high))