2014
03-01

# 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，求最少需要多少个点可以把所有的点覆盖。。。

#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;
}

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

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