【ybtoj 贪心】B. 3.砍树问题

• 题面
• 解题思路
• Code

ybtoj 贪心 B. 3.砍树问题

小小的勾股一下， 可以发现，a 不遮挡 b，a到b的距离必须 ≥ a的高度
因为树之间的距离是固定的，所以a的允许高度是固定的

注意这里的遮挡并不是只有邻近的两棵树之间会遮挡，而是任意两棵树都是有可能遮挡的
所以决定 a 的高度，就必须找到一颗离 a 最近的树，使a到b的距离最小，这样a的高度才oK

按位置将树从左到右排一下，那么只有邻近两个树，才可能是离 a 最近的树，然后两个距离比较一下就好了

#include 

using namespace std;

struct DT{
	int pos, high;
}a[100100];
int n, h;

bool cmp(const DT&k, const DT&l) {
	return k.pos < l.pos;
}

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++)
		scanf("%d %d", &a[i].pos, &a[i].high);
	sort(a + 1, a + 1 + n, cmp);
	
	h += max(0, a[1].high - (a[2].pos - a[1].pos));  //首尾特别处理
	h += max(0, a[n].high - (a[n].pos - a[n - 1].pos));
	
	for(int i = 2; i < n; i ++) 
		h += max(0, a[i].high - min(a[i].pos - a[i - 1].pos, a[i + 1].pos - a[i].pos));
	printf("%d", h);
}