/**
* 直线上有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] + ",");
}
}
}
Saruman's Army
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 1 卢照邻（634--685），字升之，幽州范阳（今河北涿县）人。 卢照邻是初唐四杰的成员之一，他的家族范阳卢氏，...
