题解：CF538C Tourist's Notes

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

即为答案。

代码展示

CPP

#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;//换行是个好习惯 
}

题解：CF538C Tourist's Notes

文章操作

CF528C 题目传送门

题目大意

解决思路

代码展示

相关推荐

评论

题解：CF538C Tourist's Notes