Codeforces Round #340 Watering Flowers

题目：

http://www.codeforces.com/contest/617/problem/C

自己感觉是挺有新意的一个题目，乍一看挺难得（= =）。

其实比较容易想到的一个笨办法就是：分别计算出每个点到喷泉的距离，然后分别按照距离远近排序（要用到两个数组），然后选定一个喷泉，从近到远依次选点，然后标记该点，从另一个喷泉中找到距离他最远且还没用被标记的点，这个距离加前一个喷泉的距离就是要求的答案，选最小的即可，n方的时间复杂度。

需要注意的几点：

1、对于每个点最好用结构体，保存距离的同时保存坐标。因为后面涉及到对两个数组进行排序，排序后还要从第二个喷泉对应的数组中找到与第一个喷泉所选的同一个点。这两个数组的排序是不同的，所以需要根据坐标寻找。

2、用于标记的数组一定是先从第二个喷泉对应数组找到点，对这个的点的下标进行标记。

3、有一种特殊情况是，第一个喷泉距离为0，第二个喷泉完全覆盖所有点。

 1 #include<stdio.h>
 2 #include<algorithm>
 3 #define maxn 2005
 4 using namespace std;
 5 
 6 struct node{
 7     int x;
 8     int y;
 9     long long d;
10 };
11 node d1[maxn];
12 node d2[maxn];
13 int book[maxn];
14 long long n,x1,y1,x2,y2;
15 //快排 
16 void quicksort(int left,int right,node d[]){
17     if(left>right)
18         return;
19     int i = left,j = right;
20     node temp = d[left];
21     while(i!=j){
22         while(d[j].d>=temp.d && i<j)
23             j--;
24         while(d[i].d<=temp.d && i<j)
25             i++;
26         if(i<j){
27             node t = d[i];
28             d[i] = d[j];
29             d[j] = t;
30         }
31     }
32     d[left] = d[i];
33     d[i] = temp;
34     
35     quicksort(left,i-1,d);
36     quicksort(i+1,right,d);
37 }
38 //保存点与计算距离 
39 void getd(long long x,long long y,int index){
40     d1[index].x = x;
41     
42     d1[index].y = y;
43     d2[index].x = x;
44     d2[index].y = y;
45     d1[index].d = (x-x1)*(x-x1) + (y-y1)*(y-y1);
46     d2[index].d = (x-x2)*(x-x2) + (y-y2)*(y-y2);
47 }
48 int main(){
49     scanf("%I64d%I64d%I64d%I64d%I64d",&n,&x1,&y1,&x2,&y2);
50     for(int i = 0;i<n;i++){
51         long long x,y;
52         scanf("%I64d%I64d",&x,&y);
53         getd(x,y,i);
54     }    
55     
56     quicksort(0,n-1,d1);
57     quicksort(0,n-1,d2);
58     
59     long long ans = d2[n-1].d;//特殊情况，第二个喷泉全部覆盖 
60     for(int i = 0;i<n;i++){
61         for(int j = 0;j<n;j++){//从第二个数组里寻找 
62             if(d1[i].x == d2[j].x && d1[i].y == d2[j].y){
63                 book[j] = 1;
64                 break;
65             }
66         }
67         //找到第二个数组里最大的未标记的点 
68         int t = n-1;
69         while(book[t] == 1 && t>=0){
70             t--;
71         }
72         ans = min(ans,d1[i].d+d2[t].d);
73     }
74     printf("%I64d
",ans);
75     return 0;
76 }

Codeforces Round #340 Watering Flowers

相关推荐