526互联

PAT Basic 1098. 岩洞施工

发布时间 2023-04-15 15:13:15作者: 十豆加日月

PAT Basic 1098. 岩洞施工

1. 题目描述：

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

fig.JPG

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

2. 输入格式：

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

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

3. 输出格式：

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

4. 输入样例：

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

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

5. 输出样例：

Yes 1

No 1

6. 性能要求：

Code Size Limit
16 KB
Time Limit
400 ms
Memory Limit
64 MB

思路：

关键在于统计出顶部轮廓的最低高度minOfTop和底部轮廓的最高高度maxOfBot，如果minOfTop>maxOfBot，说明至少有1个单位的高度差，可以直接施工。否则就不能直接施工，需要找出至少削掉的高度，如果削掉顶部轮廓，则顶部轮廓的最低高度应为maxOfBot + 1，这里计算顶部轮廓至少需要削掉cutOffTop = (maxOfBot + 1) - minOfTop，类似的底部轮廓至少需要削掉cutOffBot = maxOfBot - (minOfTop - 1);，最后进行比较输出即可。

My Code:

#include <stdio.h>

int main(void)
{
    int n;
    int top[100] = {0};
    int bottom[100] = {0};
    int maxOfBot=-1, minOfTop=1001;
    int cutOffTop = 0, cutOffBot = 0;
    
    scanf("%d", &n);
    for(int i=0; i<n; ++i) // input top height
    {
        scanf("%d", &top[i]);
        if(minOfTop > top[i]) minOfTop = top[i];
    }
    for(int i=0; i<n; ++i) // input bottom height
    {
        scanf("%d", &bottom[i]);
        if(maxOfBot < bottom[i]) maxOfBot = bottom[i];
    }
    
    if(minOfTop > maxOfBot) // can work directly
    {
        printf("Yes %d\n", minOfTop-maxOfBot);
    }
    else // can't work directly
    {
        cutOffTop = (maxOfBot + 1) - minOfTop; // cut off top
        cutOffBot = maxOfBot - (minOfTop - 1); // cut off bottom
        printf("No %d\n", cutOffTop<cutOffBot? cutOffTop : cutOffBot);
    }
    
    return 0;
}