聰聰研究發現，荒島野人總是過著群居的生活，但是，并不是整個荒島上的所有野人都屬于同一個部落，野人們總是拉幫結派形成屬于自己的部落，不同的部落之間則經常發生爭斗。只是，這一切都成為謎團了——聰聰根本就不知道部落究竟是如何分布的。 不過好消息是，聰聰得到了一份荒島的地圖。地圖上標注了N個野人居住的地點（可以看作是平面上的坐標）。我們知道，同一個部落的野人總是生活在附近。我們把兩個部落的距離，定義為部落中距離最近的那兩個居住點的距離。聰聰還獲得了一個有意義的信息——這些野人總共被分為了K個部落！這真是個好消息。聰聰希望從這些信息里挖掘出所有部落的詳細信息。他正在嘗試這樣一種算法： 對于任意一種部落劃分的方法，都能夠求出兩個部落之間的距離，聰聰希望求出一種部落劃分的方法，使靠得最近的兩個部落盡可能遠離。 例如，下面的左圖表示了一個好的劃分，而右圖則不是。請你編程幫助聰聰解決這個難題。 
輸出一行，為最優劃分時，最近的兩個部落的距離，精確到小數點后兩位。
JSOI2010第二輪Contest1
思路：
首先，考慮這個距離是具有單調性的，（距離越大，分出來的組越少），那么我們二分這個距離，對于小于這個距離的，分到一組，否則不能分到一組。
對于二分出來的這個距離，分組結束后，統計分組個數，如果分組個數大于等于K個，增大這個二分值，否則減少這個二分值。
對于eps的判定，1e-6是可過的（1e-3有點大沒過去.....）；
維護答案，輸出最終答案即可。
對于這個題的解法，看到網上大部分的最小生成樹的思路更加高效：
①對于一個部落來講，可以是一個點，當然也可以多個點。
②那么我們不妨貪心來做，首先按照邊從小到大排序，接下來對于權值較小的邊開始合并.直到合并到n-k條邊的時候.大集合作為一個部落，之外的那些點每個點作為一個部落的話，此時就有K個部落了，那么這個最近的距離就是接下來的那條邊，那么就第n-k+1條樹邊。
③這個思路也是蠻好的，記錄一下，將問題巧妙轉化，變成求第n-k+1條最小生成樹邊。
Ac代碼（窩寫的二分的）：
#include<stdio.h>#include<string.h>#include<math.h>using namespace std;#define eps 1e-6double x[100200];double y[100200];double dis[1005][1005];int f[1005];int n,m;int find(int a){ int r=a; while(f[r]!=r) r=f[r]; int i=a; int j; while(i!=r) { j=f[i]; f[i]=r; i=j; } return r;}int merge(int a,int b){ int A,B; A=find(a); B=find(b); if(A!=B) { f[B]=A; }}int Slove(double mid){ for(int i=1;i<=n;i++)f[i]=i; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(dis[i][j]<mid) { merge(i,j); } } } int cnt=0; for(int i=1;i<=n;i++) { if(f[i]==i)cnt++; } if(cnt<m)return 1; else return 0;}int main(){ while(~scanf("%d%d",&n,&m)) { for(int i=1;i<=n;i++) { scanf("%lf%lf",&x[i],&y[i]); } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { dis[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])); } } double ans=-1; double l=0; double r=1000000000000; while(r-l>eps) { double mid=(l+r)/2; if(Slove(mid)==1) { ans=mid; r=mid; } else l=mid; } PRintf("%.2lf/n",ans); }}
新聞熱點
疑難解答
