Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：给出n个x轴上的坐标点，选取其中c个，问c个之中任意两个点的最小距离最大是多少。
思路：二分距离check合法性。
大水题。。。因为想把三分艹掉。。。三分的题又多和二分挂在一起。。。顺便就写了。。。。
代码实现
1/* ***********************************************
2Author :111qqz
3Created Time :Mon 19 Sep 2016 10:57:54 PM CST
4File Name :code/poj/2456.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31const int N=1E5+7;
32int x[N];
33int n,c;
34bool check( int k)
35{
36 int cnt = 1;
37 int cur = x[1];
38 for ( int i = 2 ; i <= n ; i++)
39 {
40 if (x[i]-cur>=k)
41 {
42 cnt++;
43 cur = x[i];
44 }
45 }
46 return cnt>=c;
47}
48int bin()
49{
50 int l = 1;
51 int r = x[n]-x[1];
52 while (l<=r)
53 {
54 int mid = (l+r)>>1;
55 if (!check(mid))
56 {
57 r = mid-1;
58 }
59 else
60 l = mid+1;
61 }
62 return l-1;
63}
64int main()
65{
66 #ifndef ONLINE_JUDGE
67 freopen("code/in.txt","r",stdin);
68 #endif
69 scanf("%d%d",&n,&c);
70 for ( int i = 1 ; i <= n ; i++) scanf("%d",&x[i]);
71 sort(x+1,x+n+1);
72 int ans = bin();
73 printf("%d\n",ans);
74 #ifndef ONLINE_JUDGE
75 fclose(stdin);
76 #endif
77 return 0;
78}