poj 2456 Aggressive cows 二分答案

缘起

日常浪费生命 poj 2456 Aggressive cows

分析

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
FJ为M头小牛盖了N间牛舍. i(1<=i<=N)号牛舍在x轴的xi位置. FJ希望将牛安排进入牛舍使得牛之间的最小距离
最大化. 问最大的最小距离是多少?

【输入】
N,M 然后是N行表示xi们
2<=N<=100000
2<=M<=N
0<=xi<=1e9

【输出】
最大的最小距离

【样例输入】
5 3
1
2
8
4
9

【样例输出】
3

【限制】
1s

【hint】
三头小牛分别住进1、4、9三间牛舍, 最小距离是4-1=3.

显然是二分答案, 因为答案具备单调性. 

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
//#include "stdafx.h"

#include <stdio.h>
//#define LOCAL
#include <algorithm>
using namespace std;

int n,m,x[100005];

bool ck(int d) // M头小牛最小距离为d可以吗?
{
	int i = 1,location = 0; // 从第2头小牛开始考察, 从贪心的角度, 第一头牛显然是不需要考察的, 因为第一头牛显然应该在第一个牛舍(location=0表示这一点)
	while(i<m) // 只要没考察完所有的小牛，考察第i+1头牛的牛舍
	{
		int dd = x[location]+d; // 第i+1头小牛的牛舍的位置需要>=dd
		while(location<n && x[location]<dd) // 只要还没考察完所有的牛舍并且当前考察的牛舍还不够dd就继续考察
		{
			location++;
		} // 要么location = n, 要么x[location]>=dd 合格了
		if (location==n)
		{
			return false;
		}
		i++; // 考察下一头牛应该住进的牛舍
	}
	return true;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d", &n,&m);
	for (int i = 0; i<n;i++)
	{
		scanf("%d", x+i);
	}
	sort(x,x+n);
	int lo = 0, hi = x[n-1]-x[0], mid, ans = -1;
	while (lo<=hi)
	{
		mid = ((lo&1)&&(hi&1))?(lo>>1)+(hi>>1)+1:(lo>>1)+(hi>>1); // 因为xi可达10亿,所以不能写成(lo+hi)>>1 防止整型溢出,而会和(lo+hi)>>1不同的只有lo和hi都是奇数的情况
		if (ck(mid))
		{
			ans = mid;
			lo = mid+1;
		}
		else
		{
			hi = mid-1;
		}
	}
	printf("%d\n", ans);
	return 0;
}

ac情况

Status Accepted
Time 141ms
Memory 488kB
Length 1080
Lang C++
Submitted 2019-09-01 15:30:22
Shared
RemoteRunId 20823420