CF545C

给 n 棵树在一维数轴上的坐标，以及它们的⾼度。现在要你砍倒 这些树，树可以向左倒也可以向右倒，砍倒的树不能重合、当然 也不能覆盖其他的树原来的位置，现在求最⼤可以砍倒的树的数 目。 1 ≤ n ≤ 10^5 , 1 ≤ xi , hi ≤ 10^9

思路：贪心：能往左倒就尽量往左倒，否则就往又倒，证明：

首先对于一颗树，如果他能往左边倒下，对于后面的每一颗树没有任何影响，所以往左边倒必定是优的。

如果不能往左边倒而是要往右边倒下，考虑代价和贡献：

贡献：答案+1；

代价：由于不能越过右边的第一颗树，所以最坏的结果是右边的第一颗树不能倒下，代价最多是 -1 ；

在贪心中，只要一种贪心策略能够让答案不会变差，那么这个贪心策略就是最优秀的，而我们的贪心策略中最坏的结果是贡献和代价相抵消，所以答案必定是最优的；

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
#define maxn 100010
#define ll long long
#define IL inline
#define clear(a) memset(a,0,sizeof a)

ll n,ans;
struct edge{
    ll id,h,lef,rig;
}e[maxn];

IL void read(ll &x){
    x=0;int f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0',ch=getchar();}x*=f;
}

int main()
{
    read(n);
    for(int i=1;i<=n;i++)
        read(e[i].id),read(e[i].h);
    for(int i=1;i<=n;i++){
        if(i==1)e[i].lef=1e14,e[i].rig=e[i+1].id-e[i].id-1;
        else if(i==n)e[i].lef=e[i].id-e[i-1].id-1,e[i].rig=1e14;
        else e[i].lef=e[i].id-e[i-1].id-1,e[i].rig=e[i+1].id-e[i].id-1;
    }
    for(int i=1;i<=n;i++){
        if(e[i].lef>=e[i].h)
            ans++,e[i-1].rig-=e[i].h;
        else if(e[i].lef<e[i].h&&e[i].rig>=e[i].h)
            ans++,e[i+1].lef-=e[i].h;
    }
    cout<<ans<<"
";
    return 0;
}