P5199 Mountain View S 题解

Motbloveut221 · 2025-11-06 23:33:47 · 题解

上手毫无头绪，但稍作分析就能发现这玩意本质上还是个区间覆盖问题

毕竟考虑一个左右两端区间完全被一个更大的区间覆盖的小山，它不可能出头的，你拼高度也拼不过

而假设有一端没有被任何区间覆盖，那它就一定能出头

而后我们可以做一些更细致的分析

1.假设我的左端点比你的左端点大，右端点比累计最大的右端点大，我出头（截止我），反之出不了头

2.假设我的左端点和你的左端点一致：

·我的右端点比累计最大的右端点大，我出头（截止我）

·我的右端点小于等于累计最大的右端点，我出不了头

换言之，如果左边（左端点更小或相等）的山都无法覆盖当前这座山，那它就一定能出头，而至于是否覆盖，是最大右端点决定的

单调栈是个不错的做法，也可以sort一遍，我的思路是sort

#include<iostream>
#include<algorithm>
using namespace std;
struct mountain{
    int start,end;
    int height;
}view[100005];
bool cmp(mountain a, mountain b){
    if(a.start!=b.start)return a.start<b.start;
    return a.end>b.end;
}
int n; 
int main(){
    cin >> n;
    for(int i=0;i<n;i++){
        int x;
        cin >> x >> view[i].height;
        view[i].start = x-view[i].height;
        view[i].end = x+view[i].height;
    }
    sort(view,view+n,cmp);
    int ans = 0;
    int rightest = -2147483647;
    for(int i=0;i<n;i++){
        if(view[i].end>rightest){
            rightest = view[i].end;
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}