贪心算法部分题目总结

使用贪心算法时，我们可以将问题简单化，贪心本就是分步求最优解，最终得到最优解的过程。将问题简单化更是贪心算法的一个重要策略。

将问题简化的方式有很多，比如我们可以从应用问题中提取出数学问题，再从数学问题中思考求解出数学函数（简单算法）解题，下面说一个数学问题中二维平面问题转化为一维数轴问题的例子：

Assume the coasting is an infinite straight line. Land is in one side of coasting, sea in the other. Each small island is a point locating in the sea side. And any radar installation, locating on the coasting, can only cover d distance, so an island in the sea can be covered by a radius installation, if the distance between them is at most d.

We use Cartesian coordinate system, defining the coasting is the x-axis. The sea side is above x-axis, and the land side below. Given the position of each island in the sea, and given the distance of the coverage of the radar installation, your task is to write a program to find the minimal number of radar installations to cover all the islands. Note that the position of an island is represented by its x-y coordinates.

Figure A Sample Input of Radar Installations

Input
The input consists of several test cases. The first line of each case contains two integers n (1<=n<=1000) and d, where n is the number of islands in the sea and d is the distance of coverage of the radar installation. This is followed by n lines each containing two integers representing the coordinate of the position of each island. Then a blank line follows to separate the cases.

The input is terminated by a line containing pair of zeros
Output
For each test case output one line consisting of the test case number followed by the minimal number of radar installations needed. “-1” installation means no solution for that case.
Sample Input

Sample Output

Case 1: 2
Case 2: 1

这道题类似于上次STL中的信号塔问题，规定一座信号源及其覆盖区域，问如何建立规定的信号源才能使其覆盖范围最大（最优解问题）/给出规定的信号源覆盖区域，求如何建信号源才能使之将规定数据全部覆盖（求信号源数量）

对于第一个问题，我们可以尝试按规定好的信号塔数量进行一一累加同时减去其所有信号塔的重复范围内的数据个数，最终求解比较取最大值。对于第二个问题，我们可以将平面问题简单化，全部将其放于数轴上进行研究，对比覆盖范围距离平方与其到数轴上的距离和该投影点到信号塔平方和之间的大小，从而确定所要建的信号塔数量。

具体代码如下：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
struct island
{
	int x, y;
	double l, r;
};
int n;
int d;
island a[1000];
bool cmp(island a, island b)
{
	if (a.r == b.r)
		return a.l < b.l;
	return a.r < b.r;
}
int main()
{
	int c = 1;
	while (~scanf("%d %d", &n, &d) && !(n == 0 && d == 0))
	{
		int num = 1,flag=0;
		for (int i = 0; i < n; i++)
		{
			scanf("%d %d", &(a[i].x), &(a[i].y));
			if (a[i].y < 0)
				flag = 1;
			else if (a[i].y>d)
				flag = 1;
		}
		if (flag)
		{
			printf("Case %d: -1\n", c++);
			continue;
		}if(d<0)
		{
			printf("Case %d: -1\n", c++);
			continue;
		}
		if (d == 0)
		{
			for (int i = 0; i < n; i++)
			{
				if (a[i].y != 0)
				{
					printf("Case %d: -1\n", c++);
					break;
				}
				if (i == n - 1)
					printf("Case %d: %d",c++,n);
			}
			continue;
		}

		for (int i = 0; i < n; i++)
		{
			a[i].l = double(a[i].x) - sqrt(double(d*d - a[i].y*a[i].y));
			a[i].r = double(a[i].x) + sqrt(double(d*d - a[i].y*a[i].y));
		}

		sort(a, a + n, cmp);
		double key=a[0].r;
		for (int i = 1; i < n; i++)
		{
			if (a[i].r == key)
				continue;
			else
			{
				if (a[i].l > key)
				{
					num++;
					key = a[i].r;
				}
			}
		}
		printf("Case %d: %d\n",c++,num);
	}
}

另外还有一个印象比较深的题目好像是输入输出问题上，cin,cout的效率要远远低于scanf();printf();使用cin,cout不能过的题目用scanf();printf();就可以过了。（cin,cout存在缓冲区，缓冲区又称为缓存，它是内存空间的一部分。也就是说，在内存空间中预留了一定的存储空间，这些存储空间用来缓冲输入或输出的数据，这部分预留的空间就叫做缓冲区。）