Airport（未解决。。。）

时间：2023-03-09 08:00:52
Airport（未解决。。。）

Airport

Time Limit: 3000/1500 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1534    Accepted Submission(s): 486

Problem Description
The country of jiuye composed by N cites. Each city can be viewed as a point in a two- dimensional plane with integer coordinates (x,y). The distance between city i and city j is defined by dij = |xi - xj| + |yi - yj|. jiuye want to setup airport in K cities among N cities. So he need your help to choose these K cities, to minimize the maximum distance to the nearest airport of each city. That is , if we define di(1 ≤ i ≤ N ) as the distance from city i to the nearest city with airport. Your aim is to minimize the value max{di|1 ≤ i ≤ N }. You just output the minimum.
Input
The first line of the input is T (1 ≤ T ≤ 100), which stands for the number of test cases you need to solve.

The first line of each case contains two integers N ,K (1 ≤ N ≤ 60,1 ≤ K ≤ N ),as mentioned above.

The next N lines, each lines contains two integer xi and yi (-109 ≤ xi, yi ≤ 109), denote the coordinates of city i.

Output
For each test case, print a line “Case #t: ”(without quotes, t means the index of the test case) at the beginning. Then a single integer means the minimum.
Sample Input
2
3 2
0 0
4 0
5 1
4 2
0 3
1 0
3 0
8 9
Sample Output
Case #1: 2
Case #2: 4

题意：就是给你一系列点，让你挑k个点建造飞机场，然后求剩下点到最近的飞机场的最小的最大距离；距离定义：dij = |xi - xj| + |yi - yj|

我的思路是分别找出每个点到剩下点的距离，然后sort排序，找出每个城市第k大值的最小值；

大婶们说这是DLX可重复覆盖：

下面是大神的说法：

HDU 2295 Radar（DLX可重复覆盖）差不多，我们的做法就是

保存n个城市之间的距离，sort一下，二分结果，对满足条件的DLX求覆盖程度，

求出最大距离最小值。此题二分0~INF也可解决。

http://www.2cto.com/kf/201412/364538.html

先把我的wa代码扔着，抽空补上。。。

wa代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<vector>

#include<algorithm>

using namespace std;

#define mem(x,y) memset(x,y,sizeof(x))

const int MAXN=1e5+10;

int a[65][65];

int cmp(int a,int b){

	return a>b;

}

struct Node{

	int x,y;

};

Node dt[65];

int getl(Node a,Node b){

	return abs(a.x-b.x)+abs(a.y-b.y);

}

int main(){

	int T,N,K,kase=0;

	scanf("%d",&T);

	while(T--){

		scanf("%d%d",&N,&K);

		for(int i=0;i<N;i++){

			scanf("%d%d",&dt[i].x,&dt[i].y);

		}

		for(int i=0;i<N;i++)for(int j=0;j<N;j++){

			a[i][j]=getl(dt[i],dt[j]);

		}

		for(int i=0;i<N;i++)sort(a[i],a[i]+N,cmp);

	/*	for(int i=0;i<N;i++){

			for(int j=0;j<N;j++)printf("%d ",a[i][j]);

			puts("");

		}*/

		int mx=0x3f3f3f3f;

		for(int i=0;i<N;i++)mx=min(mx,a[i][K-1]);

		printf("Case #%d: %d\n",++kase,mx);

	}

	return 0;

}

　　

相关文章