[数据结构与算法]Codeforces Round #303 (Div. 2)C(Woodcutters)

原题目链接： https://codeforces.com/problemset/problem/545/C

先简单翻译下题目意思：在一个坐标上，输入的n个位置上各有一棵树，高度为hi,坐标为(xi,0),它可以往左或者往右倒下，范围是（xi-hi,xi)或者(xi,xi+hi)。但是，倒下时必须不在原先倒下树的范围内，找到倒下树的最大值。

思路：先特殊处理，当n=1时，输出1；
当n=2时，输出2；（两棵树一个往左，一个往右倒）
一般考虑：遍历n-2次，从x[1]开始，每次判断该树与左边的树的距离是否大于本身的高度，如果大于，则s加一；如果不是，再判断后面一个树与当前树的距离是否大于本身的高度，如果大于，则树向右倒，树的坐标更新为当前坐标加上本身的高度。

public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();//有n棵树
        int h[]=new int[n];//各个树的高度数组
        int x[]=new int[n];//各个树的坐标数组
        for(int i=0;i<n;i++) {//存入各个树的坐标和各个树的高度
            x[i]=sc.nextInt();
            h[i]=sc.nextInt();
        }
        int s = 2;//如果n>=3的话，初始化时，至少有两棵树可以倒下
        if(n < 3) System.out.println(n);
        else {
            for (int i = 1; i < n - 1; i++) {
                if (x[i] - x[i - 1] > h[i]) s++;//树向左倒
                else if (x[i + 1] - x[i] > h[i]) {
                    s++;
                    x[i] = x[i] + h[i];//说明树是向右倒的，要把坐标更新为加上自己的高度
                }
            }
            System.out.println(s);
        }
    }