题意:已知n棵树坐标x及其高度h,现在要求最多能砍多少棵树。要求:砍一棵树后,其所占有的区间是 [x-h,x] or [x,x+h] 要求树倒下后所占的区间不能先前被其他树占领过。
思路:对于2棵以上的树,首先 最左右 两棵树必定往左边和右边倒。
对于i=2~n-1的树,对于当前的i,先尝试 能不能放左边 ,左边不行,放右边,右边还不行不放。 理由是:对于两棵树,要么只能放一棵(任意一棵),要么两颗都放,要么都不放。
数据分析:(!注意数据!)1 ≤ n ≤ 1e5 1 ≤ x[i], h[i] ≤ 1e9
复杂度分析:O(n)
错误原因:没考虑到n=1的情况,直接默认n>=2 。 数据观察还是很重要的。对于你当前的算法,可能你需要特判一些特殊的数据。吃一堑长一智。还有我是wa9点。一般这样可以说明你的算法没什么大问题。注意是否爆int , 以及特殊情况下是不是漏判即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+50;
struct node
{
ll x,h,r,l,vis;//h,r保存当前区间范围,vis记录这棵树往哪里倒
}t[maxn];
ll ans=2;
int main(void)
{
ll n;
cin >> n;
for(int i=1;i<=n;i++)
{
scanf("%I64d%I64d",&t[i].x,&t[i].h);
t[i].l=t[i].r=t[i].x;t[i].vis=0;/**-1左,0中,1右 **/
}
if(n==1)// 注意n=1的情况
{
cout << "1" << endl;
return 0;
}
t[1].vis=-1,t[n].vis=1,t[1].l=t[1].x-t[1].h,t[n].r=t[n].x+t[n].h;
for(int i=2;i<=n-1;i++)
{
if(t[i-1].vis==-1 || t[i-1].vis==0)//前面的树不动或者往左倒是一类
{
if(t[i].h<t[i].x-t[i-1].x)
{
t[i].vis=-1;
t[i].l=t[i].x-t[i].h;
ans++;
}
else if(t[i].h<t[i+1].x-t[i].x)
{
t[i].vis=1;
t[i].r=t[i].x+t[i].h;
ans++;
}
else
t[i].vis=0;
}
else if(t[i-1].vis==1)//往右倒是一类
{
if(t[i].h<t[i].x-t[i-1].r)
{
t[i].vis=-1;
t[i].l=t[i].x-t[i].h;
ans++;
}
else if(t[i].h<t[i+1].x-t[i].x)
{
t[i].vis=1;
t[i].r=t[i].x+t[i].h;
ans++;
}
else
t[i].vis=0;
}
}
cout << ans << endl;
}