题解：CF538C Tourist's Notes

· · 题解

思路：

这道题题意很明确，用 pair 把天数与海拔存下来，判断两个记录之间能达到的最大海拔是多少最后输出答案即可。

要注意一下，第 1 天到第一次输入的那一天和最后一次输入到结束的那些天也要计入答案。

代码

#include <bits/stdc++.h>
using namespace std;
int n,m;
int main() {
    cin>>n>>m;
    vector<pair<int,int> >a(m);
    for(int i=0;i<m;++i) cin>>a[i].first>>a[i].second;
    sort(a.begin(),a.end());
    int mx=max(a[0].second+a[0].first-1,a.back().second+(n-a.back().first));
    for(int i=1;i<m;++i){
        int h=abs(a[i].second-a[i-1].second),d=a[i].first-a[i-1].first;
        if(h>d){
            cout<<"IMPOSSIBLE\n";
            return 0;
        } 
        mx=max(mx,max(a[i].second,a[i-1].second)+(d-h)/2);
    }
    cout<<mx<<endl;
    return 0;
}