POJ2456题解

发表于 | 更新于 | 评论数： | 阅读次数：

qbxt上课讲5min就过了的题，$Herself32$做了15min+，说明Ta实在是菜死了。

题目描述

Farmer John has built a new long barn, with N (2 <= N <= 100,000) stalls.

The stalls are located along a straight line at positions x1,…,xN (0 <= xi <= 1,000,000,000).

His C (2 <= C <= N) cows don’t like this barn layout and become aggressive towards each other once put into a stall.

To prevent the cows from hurting each other, FJ want to assign the cows to the stalls, such that the minimum distance between any two of them is as large as possible.

What is the largest minimum distance?

输入输出格式

输入格式

Line 1: Two space-separated integers: N and C

Lines 2..N+1: Line i+1 contains an integer stall location, xi

输出格式

Line 1: One integer: the largest minimum distance

INPUT & OUTPUT’s examples

Input’s eg #1

1
2
3
4
5
6
5 3
1
2
8
4
9

Output’s eg #1

1
3

Hint

OUTPUT DETAILS:

FJ can put his 3 cows in the stalls at positions 1, 4 and 8, resulting in a minimum distance of 3.

Huge input data,scanf is recommended.

分析

qbxt的ysq奆佬用了5min-就讲完了这题，还包括一个秀儿秀了半天。

。。。自闭了

比较裸的一个二分，但是我们要对于答案进行二分，也就是二分答案。

我们首先把第一头牛放进牛栏，并开一个front变量表示当前被放入牛栏的牛的编号。

然后枚举剩下的牛栏，如果这些牛栏与front之间的间距大于等于$k$,就是Judge函数传进来的值。

当所有的牛都被放完后，返回true。

然后我们对于答案进行二分，我们定义l为最小距离，就是1，最大距离r为牛栏编号最大的减去编号最小的.

然后进行二分，如果这些牛能够被照题意分进牛栏里，那么就把l=mid+1，查找右区间。

如果不能，把r=mid，查找左区间。

最后$r-1$即为答案。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/* Headers */
#include<cstdio>
#include<cmath>
#include<cctype>
#include<cstring>
#include<algorithm>
namespace FastIO{
    const int BUFSIZE=1<<20;
    char ibuf[BUFSIZE],*is=ibuf,*its=ibuf;
    char obuf[BUFSIZE],*os=obuf,*ot=obuf+BUFSIZE;
    inline char getch(){
        if(is==its)
            its=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is==its)?EOF:*is++;
    }
    inline int getint(){
        int res=0,neg=0,ch=getch();
        while(!(isdigit(ch)||ch=='-')&&ch!=EOF)
            ch=getch();
        if(ch=='-'){
            neg=1;ch=getch();
        }
        while(isdigit(ch)){
            res=(res<<3)+(res<<1)+(ch-'0');
            ch=getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os=obuf;
    }
    inline void putch(char ch){
        *os++=ch;
        if(os==ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)	putch('0');
        else if(res<0){
            putch('-');
            res=-res;
        } 
        int top=0;
        while(res){
            q[top++]=res%10+'0';
            res/=10;
        }
        while(top--)	putch(q[top]);
    }
} 
using namespace FastIO;
/* definitions */
const int MAXN = 1e6+10;
int cow[MAXN],n,m;
/* functions */
inline void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&cow[i]);
	}
}
inline bool Judge(int k){
	int front=cow[1];
	int num=1;
	for(int i=2;i<=n;i++){
		if(cow[i]-front>=k){
			front=cow[i];
			num++;
		}
		if(num>=m)return true;
	}
	return false;
}
inline void binary_search(){
	int l=1,r=cow[n-1]-cow[0];
	int mid=(l+r)>>1;
	if(Judge(mid))l=mid+1;
	while(l<r){
		else r=mid;
	}
	printf("%d\n",r-1);
}
int main(int argc,char *argv[]){
	init();
	std::sort(cow+1,cow+n+1);
	binary_search();
	return 0;
}

THE END