UVa 10382 - Watering Grass（貪心算法，區間覆蓋問題）

Problem E
Watering Grass
Input: standard input
Output: standard output
Time Limit: 3 seconds

n sprinklers are installed in a horizontal strip of grass l meters long andw meters wide. Each sprinkler is installed at the horizontal center line of the strip. For each sprinkler we are given its position as the distance from the left end of the center line and its radius of operation.

What is the minimum number of sprinklers to turn on in order to water the entire strip of grass?

Input

Input consists of a number of cases. The first line for each case contains integer numbersn, l and w with n <= 10000. The next n lines contain two integers giving the position of a sprinkler and its radius of operation. (The picture above illustrates the first case from the sample input.)

Output

For each test case output the minimum number of sprinklers needed to water the entire strip of grass. If it is impZ喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vc3NpYmxlIHRvIHdhdGVyIHRoZSBlbnRpcmUgc3RyaXAgb3V0cHV0IC0xLjwvcD4KPGgzPlNhbXBsZSBpbnB1dDwvaDM+CjxwPjggMjAgMjwvcD4KPHA+NSAzPC9wPgo8cD40IDE8L3A+CjxwPjEgMjwvcD4KPHA+NyAyPC9wPgo8cD4xMCAyPC9wPgo8cD4xMyAzPC9wPgo8cD4xNiAyPC9wPgo8cD4xOSA0PC9wPgo8cD4zIDEwIDE8L3A+CjxwPjMgNTwvcD4KPHA+OSAzPC9wPgo8cD42IDE8L3A+CjxwPjMgMTAgMTwvcD4KPHA+NSAzPC9wPgo8cD4xIDE8L3A+CjxwPjkgMTwvcD4KPHA+IDwvcD4KPHByZSBjbGFzcz0="brush:java;">Sample Output

6

2

-1

思路：

貪心思想，將問題轉化為區間覆蓋問題，將草地的上邊界作為要覆蓋的區間，計算出每個灑水器覆蓋的區間范圍，不能覆蓋的捨去，然後將灑水器按覆蓋范圍的左邊界升序排列。

要覆蓋的最右邊的點rightmost的初始值為0，遍歷灑水器，找一個能覆蓋住rightmost且覆蓋范圍的右邊界最大的灑水器，然後將該灑水器覆蓋的右邊界作為新的rightmost，重復剛才的過程，直到覆蓋整個草地。

#include 
#include 
#include 
#include 
using namespace std;

#define MAX_SIZE 10000

struct Sprinkler
{
	double left;
	double right;
	bool operator < (const Sprinkler &s) const
	{
		return left < s.left;
	}
}sprinklers[MAX_SIZE+5];

int WaterTheGrass(int m, int l)
{
	double rightmost = 0.0;
	int count = 0;
	int i, j;
	for (i = 0; i < m; i = j)
	{
		if (sprinklers[i].left > rightmost) break;
		for (j = i+1; j < m && sprinklers[j].left <= rightmost; ++j)
		{
			if (sprinklers[j].right > sprinklers[i].right)
			{
				i = j;
			}
		}
		++count;
		rightmost = sprinklers[i].right;
		if (rightmost >= l) break;
	}
	if (rightmost >= l)
	{
		return count;
	}
	return -1;
}

int main(void)
{
	int n, l;
	double w;
	while (cin >> n >> l >> w)
	{
		w /= 2.0;
		int i, m = 0;
		for (i = 0; i < n; ++i)
		{
			int p, r;
			scanf("%d%d", &p, &r);
			if (r > w)
			{
				double halfCoveredLen = sqrt((double)r*r - w*w);	//注意轉化為double型，錯了好幾次...
				sprinklers[m].left = (double)p - halfCoveredLen;
				sprinklers[m++].right = (double)p + halfCoveredLen;
			}
		}
		sort(sprinklers, sprinklers+m);
		cout << WaterTheGrass(m, l) << endl;
	}
	return 0;
}