萨鲁曼的军队(Saruman's Army) 代码(C)

本文地址: http://blog.csdn.net/caroline_wendy

题目: 直线上有N个点, 每个点, 其距离为R以内的区域里, 必须带有标记的点, 本身的距离为0.

尽可能少的加入�标记点, 至少要有多少点被加上标记?

贪心算法, 从最左边的点開始, 依次查找距离为R须要加入�标记的点, 直到结束.

代码:

/*

 * main.cpp

 *

 *  Created on: 2014.7.17

 *      Author: spike

 */

/*eclipse cdt, gcc 4.8.1*/

#include <stdio.h>

#include <limits.h>

#include <utility>

#include <queue>

#include <algorithm>

using namespace std;

class Program {

	static const int MAX_N = 10000;

	int N=6, R=10;

	int X[MAX_N] = {1, 7, 15, 20, 30, 50};

public:

	void solve() {

		sort(X, X+N);

		int i=0, ans=0;

		while (i<N) {

			int s = X[i++];

			while (i<N&&X[i]<=s+R) i++;

			int p = X[i-1];

			while (i<N&&X[i]<=p+R) i++;

			ans++;

		}

		printf("result = %d\n", ans);

	}

};

int main(void)

{

	Program P;

	P.solve();

    return 0;

}

输出:

result = 3