Saruman's Army

/**
 * 直线上有N个点。点i的位置是Xi。从这N个点中选择若干个，给他们加上标记。
 * 对每一个点，其距离为R以内的区域里必须有带有标记的点(自己本身带有标记的点可以认为与其距离为0的地方有一个带有标记的点)
 * 再慢则这个条件的情况下，希望能为尽可能少的点添加标记。请问至少要有多少个点被加上标记?
 * @author haofan.whf
 * @version $Id: SarumansArmy.java, v 0.1 2018年06月14日 上午11:44 haofan.whf Exp $
 */
public class SarumansArmy {

    public void solution(int N, int[] X, int R){
        /**
         * 思路：从最左边开始选择以X0为中心，R为半径的圆中离X0最远距离的点Xn打上标记
         * 如果不存在这种点，且半径范围内无被打标的点，则本身需要打上标记
         */
        //flag[]用来保留已经被打过标的点,打过标的计为true
        boolean[] flag = new boolean[N];
        for (int i = 0; i < N; i++) {
            int current = X[i];
            //首先判断该点半径R内左边部分是否已经存在打标的点
            int left = i - 1;
            boolean needCheckRight = true;
            while (left > 0){
                if(flag[left] && current - R <= X[left]){
                    needCheckRight = false;
                    break;
                }
                left--;
            }
            if(needCheckRight){
                //此时已经到最右边的点
                //并且该点的左边没有被标记的点
                //需要单独打标
                if(i + 1 >= N){
                    flag[i] = true;
                }else{
                    //从左往右边找
                    for (int j = i+1; j < N; j++) {
                        if(current + R <= X[j]){
                            flag[j-1] = true;
                            i = j-1;
                            break;
                        }
                    }
                }
            }
        }
        for (int i = 0; i < flag.length; i++) {
            System.out.print(flag[i] + ",");
        }
    }

}