- 题面
- 解题思路
- Code
ybtoj 贪心 B. 3.砍树问题
题面
解题思路
小小的勾股一下, 可以发现,a 不遮挡 b,a到b的距离必须 ≥ a的高度
因为树之间的距离是固定的,所以a的允许高度是固定的
注意这里的遮挡并不是只有邻近的两棵树之间会遮挡,而是任意两棵树都是有可能遮挡的
所以决定 a 的高度,就必须找到一颗离 a 最近的树,使a到b的距离最小,这样a的高度才oK
按位置将树从左到右排一下,那么只有邻近两个树,才可能是离 a 最近的树,然后两个距离比较一下就好了
Code
#includeusing 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); }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)