首页 > ACM题库 > HDU-杭电 > HDU 3069-Arrest-贪心-[解题报告]HOJ
2014
03-01

HDU 3069-Arrest-贪心-[解题报告]HOJ

Arrest

问题描述 :

Country ALPC has n cities, and the cities are connected by undirected roads. Furthermore, there is exactly one route between each pair of cities. Now some criminals break the prison and the police do not know where they are. And the criminals can stay in a city or move on the roads. The police office has made a decision to send policemen to arrest the breakers. If a police and a criminal at a same point at the same time the criminal is under arrest, no matter in a city or on a road. The police office wants to minimize the number of policemen to arrest all the criminals. Now the map of Country ALPC is given, please tell the police office the least number of policemen required.

输入:

There are several test cases.
The first line a integer n, the number of cities. Next n-1 lines each two integers a and b, there is a road between city a and city b.
(1<=n <= 1000, 1 <= a, b <= n)

输出:

There are several test cases.
The first line a integer n, the number of cities. Next n-1 lines each two integers a and b, there is a road between city a and city b.
(1<=n <= 1000, 1 <= a, b <= n)

样例输入:

3
1 2
2 3
16
1 2
1 3
1 4
5 6
5 7
10 8
8 11
9 12
9 13
14 1
14 15
15 16
15 8
9 16
14  5

样例输出:

1
3

点击打开链接

题意:

x轴上有n点,每个点都有一个覆盖距离m,求最少需要多少个点可以把所有的点覆盖。。。

这里主要是要找以那个点为中心。

比如1 7 15 20 30 50 70(m=10)

刚开始用1为中心,它的覆盖距离为1-11,因为7在范围内,所以可以以7为中心,以7为中心,可以把15覆盖。ans++;

然后再以20为中心,可以找到30在20的范围内,所以更新中心点为30,然后去掉30-40范围内的点,ans++;

依此类推。。。。

综上,每次现以一个点a为中心,然后看看能否更新中心(即是否有某个点在a的距离内),然后去掉新的中心里面的点。。。

#include"stdio.h"
#include"string.h"
#include"algorithm"
using namespace std;
#define N 1005
int main()
{
	int i;
	int n,m;
	int A[N];
	while(scanf("%d%d",&m,&n)!=-1)
	{
		if(m==-1&&n==-1)break;
		for(i=0;i<n;i++)
			scanf("%d",&A[i]);
		sort(A,A+n);
		int ans=1;
		int p=A[0]+m;
		i=1;
		while(i<n)
		{
			while(i<n&&A[i]<=p)i++;
			if(i>=n)break;
			p=A[i-1]+m;
			while(i<n&&A[i]<=p)i++;
			if(i>=n)break;
			p=A[i]+m;
			ans++;
		}
		printf("%d\n",ans);
	}
	return 0;
}

参考:http://blog.csdn.net/yangyafeiac/article/details/9953243


  1. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!

  2. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧