P5199 Mountain View S 题解

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

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

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

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

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

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

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

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

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

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

CPP

#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;
}

P5199 Mountain View S 题解

文章操作

相关推荐

评论

P5199 Mountain View S 题解