题解：CF538C Tourist's Notes

OIerJiang_1017 · 2024-12-23 16:51:13 · 题解

CF528C 题目传送门

题目大意

一个人出去爬山 n 天，第 i 天所在地方的高度为 h，相邻两天的高度之差不超过 1。给出部分天数的高度，问这个人在这 n 天中，所到地方的最高高度是多少？如果根据给出的数据不符合题意描述，即出现相邻两天的高度之差超过 1，输出 IMPOSSIBLE。

解决思路

用一个结构体记录天当天高度 h 和当天天数 d。设 dd 为相隔的天数，hh 为 dd 天相隔的高度差

• 若 hh>dd，即相隔的高度比天数大（相邻两天的高度差不超过 1），则不符合题意，直接输出 IMPOSSIBLE；
• 否则就符合要求，求出相隔天数中的最大海拔高度就为 ans = max(ans, a[i].h + (hh + dd) / 2)。

最终 ans 即为答案。

代码展示

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int n, m, ans;
struct node
{
    int d, h;
    //d记录天数
    //h记录高度 
}a[N];

int main()
{
    scanf("%d%d", &n, &m);//建议scanf,更快
    for(int i = 1; i <= m; i++)
        scanf("%d%d", &a[i].d, &a[i].h);
    ans = a[1].h + a[1].d - 1;
    for(int i = 1; i < m; i++)
    {
        int dd = a[i + 1].d - a[i].d;//相隔天数
        int hh = a[i + 1].h - a[i].h;//dd天相隔的高度 
        if(abs(hh) > dd) 
        {//相隔的高度比天数大
            printf("IMPOSSIBLE\n");
            return 0;//建议printf,更快
        }
        else ans = max(ans, a[i].h + (hh + dd) / 2);
    }
    ans = max(ans, a[m].h + n - a[m].d);
    printf("%d\n", ans);
    return 0;//换行是个好习惯 
}