R的农场

题目描述

最近,R 终于获得了一片他梦寐以求的农场,但如此大的一片农场,想要做好防卫工作可不是一件容易的事。所以 R 购买了 N 个守卫,分别让他们站在一定的位置上(守卫不可移动,同一位置上至多有一个守卫)。但是,安排了所有的守卫之后,R 才发现,守卫们彼此十分厌恶。经 R 研究,当某两个守卫距离≤K,他们就会发生争吵;但是,想要守卫们和解也是不难的——只需要 R 给出的平均工资能使两人满意,他们就会同意和解、成为
朋友;当然,如果两个守卫有共同的朋友,他们也会和解成为朋友。R 非常不想守卫们争吵,因此他想找出,在能使所有守卫闭嘴的前提下,平均工资的最小值是多少。他想到了一个绝妙的方法,但他忙着去 Farm,没时间,所以这个任务就交给你了。输入

输入

第1 行为三个数 N, M, K。
接下来 N 行为 N 个守卫的位置,每行包含两个实数 x, y (x≥0, y≥0)。
接下来 M 行,每行三个数,u, v, w,代表若平均工资≥w,则 u 和 v 同意和解。

输出

输出文件有且仅有一行,一个实数 p,代表最小的平均工资。

输入输出样例

chebnear.in

5 5 1.300
1.000 1.000
2.000 3.000
3.000 2.000
2.500 6.000
6.000 3.000
2 4 1.500
5 3 2.350
1 4 0.500
4 5 2.250
3 2 3.200

chebnear.out

2.350

反思

本来想用二分答案做到,虽然我确实这么做了,但是由于我没有写完立刻就编译,想着先写后面的再来写,结果......,没有写完,我觉得我写题都要写出毛病来了,每次打完道题目,总有七七八八的东西导致我编译过不了,特别是考试的时候,编译改错要花我好久的时间..

思路

这题的思路其实我还是懂了的

1.我们二分平均工资,把那些权值满足小于等于工资的点之间连上线(其实就是用并查集归类然后再去染色,相当与联通块的染色)

2.我们染色过后,根据最近点对(最近点对就是我们先按x即横坐标排序,求出中线,那么求点之间的最短距离只可能有3种情况1.在中线左边2.在中线右边3.跨过中线相连我们可以先算出2边的最短点对之间的距离,然后我们以这个距离为标准,向左向右分别寻找在该距离之内的点,然后判断就可以了,tips,这个也是递归实现的,因为我们在寻找左右的最短点对时,左右就相当与2个独立的区间,然后我们就在区间内寻找............),我们就可以判断该工资是否合法(如果2给点是相同颜色的,我们就不会更新)

3.最后我们二分寻找答案确定了答案的精度,输出就可以啦!

代码

感觉自己要死了,写了一个晚上,还是木有写出来,我觉得我的思路一点毛病也没有,为什么就是错了!!

先放一份错的,保存一下今天晚上的"成果"!!

OK啦OK啦,我写完啦

我知道为什么我错了!!原来我把题目意思都理解错了!!!!!!!!!我是真心佩服我自己/(ㄒoㄒ)/~~

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 #define FOR(i,a,b) for(register int i=a;i<=b;i++)
 4 #define ROF(i,a,b) for(register int i=a;i>=b;i--)
 5 using namespace std;
 6 int n,m;
 7 double K;
 8 double maxx=0;
 9 int ans;
10 int fa[100010];
11 int tmpt[100011];
12 struct ss
13 {
14     int x,y;
15     double p;
16 }b[200010];
17 struct ss1
18 {
19     double X,Y;
20     int num;
21 }a[100010],c[100010];
22 int scan()
23 {
24     int as=0,f=1;
25     char c=getchar();
26     while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();}
27     while(c>='0'&&c<='9'){as=(as<<3)+(as<<1)+c-'0';c=getchar();}
28     return as*f;
29 }
30 int ba(int x) {return fa[x]=((fa[x]==x)?x:ba(fa[x]));}
31 bool cmp(ss1 i,ss1 j) {return i.X<j.X;}
32 bool cmp2(ss1 i,ss1 j) {return i.Y<j.Y;}
33 bool cmp3(ss i,ss j)   {return i.p<j.p;}
34 bool  clst(int l,int r)
35 {
36     int mid=(l+r)>>1;
37     if(l>=r) return 1;
38     if(!clst(l,mid)||!clst(mid+1,r)) return 0;
39     int k=0;
40     while(a[l].X+K<a[mid].X) l++;
41     while(a[r].X-K>a[mid].X) r--;
42     FOR(i,l,r) c[++k]=a[i];
43     sort(c+1,c+k+1,cmp2);
44     FOR(i,1,k)
45     {
46         FOR(j,i+1,k)
47         {
48             if(c[j].Y-c[i].Y>K) break;
49             if(ba(c[i].num)!=ba(c[j].num))
50             {
51                 if(abs(c[i].X-c[j].X)<=K)
52                     return 0;
53             }
54         }
55     }
56     return 1;
57 }
58 bool chek(int mid)
59 {
60     FOR(i,1,n) fa[i]=i;//父亲的赋值
61     FOR(i,1,m)
62     {
63         if(b[i].p>b[mid].p) break;
64         int f1=ba(b[i].x),f2=ba(b[i].y);//父亲的赋值
65         if(f1!=f2)
66             fa[f1]=f2;
67     }
68     return clst(1,n);
69 }
70 int main()
71 {
72     n=scan();m=scan();
73     scanf("%lf",&K);
74     FOR(i,1,n) scanf("%lf%lf",&a[i].X,&a[i].Y),a[i].num=i;
75     sort(a+1,a+n+1,cmp);//按照X的关键字排序
76     FOR(i,1,m)
77     {
78         b[i].x=scan();b[i].y=scan();scanf("%lf",&b[i].p);
79     }
80     sort(b+1,b+m+1,cmp3);//按照和解费排序
81     int l=0,r=m-1;
82     while(l<=r)
83     {
84         int mid=(l+r)>>1;
85         //cout<<mid<<endl;
86         if(chek(mid))
87         {
88             //        cout<<"NBV"<<" "<<mid<<endl;
89             r=mid-1;
90         }
91         else l=mid+1;
92     }//zh这个二分其实不是很懂...
93 //    cout<<ans-1<<endl;
94     printf("%.3lf",b[l].p);
95 }
96 //找了半天发现是排序的错,我也是佛系了.......

View Code