[笔记][中国大学mooc][程序设计与算法（二）算法基础][二分算法] 农夫和奶牛

本文主要是介绍[笔记][中国大学mooc][程序设计与算法（二）算法基础][二分算法] 农夫和奶牛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

在这里插入图片描述

分析

本题的解空间是 $[1,\frac{(10^9+1)-1}{C-1}]\bigcap{Z^+}$ （这里老师在课上讲的区间是 $[1,\frac{10^9}{C}]$ ，考虑有两头牛，牛舍在 $0$ 和 $10^9$ 的位置都存在，那么这个最大距离就应当是 $\frac{10^9-0}{1}$ ，所以这里可能有点问题，但是不影响老师所讲的二分法核心思想）另外，考虑到可以获取到最左边和左右边个隔间的位置，所以牛的最大间距就是 $[1,\frac{biggestPosition-smallest Position}{C-1}]\bigcap{Z^+}$ ,解空间进一步缩小
本题即是在上述解空间中进行二分查找。

本题目与[笔记][中国大学mooc][程序设计与算法（二）算法基础][二分算法] 派题目十分相似（核心都是二分法），但是本题目在验证某数是否属于解空间的时候，需要按顺序遍历整个隔间位置的序列。
而且本题目的解空间是离散的，在二分法中可能会出现很多问题：

递归函数必须强制收缩左右边界，意思是在验证了 $\lfloor\frac{(L+R)}{2}\rfloor$ 的可行性后，如果可行需要将左边界收缩到 $\lfloor\frac{(L+R)}{2}\rfloor+1$ 的位置，注意同时需要记住这个 $\lfloor\frac{(L+R)}{2}\rfloor$ ；否则将右边界收缩至 $\lfloor\frac{(L+R)}{2}\rfloor-1$ 。原因是如果解在 $[a, a + 1]$ ， $\lfloor\frac{(L+R)}{2}\rfloor=a$ ，如果不主动收缩左边界，下一次调用区间是不会收缩的，产生死循环。
递归函数在 $[L, R]$ 中找不到解的情况（比如上一次调用递归函数的值已经是正确的了，如果继续验证是否有更大的解，就会发生找不到解的情况），所以需要先验证左边界 $L$ 是否在解空间内。

代码

#include<stdio.h>
#define MAXN 100000
long long N, C;//C=#cows N=#stalls
long long positionOfStalls[MAXN];
//判断该距离是否能把牛全部装下
bool IsCurrentDistanceWorks(long long testDistance){long long lastCowPosition = positionOfStalls[0];long long restCows = C-1;for(int cnt=0; cnt<N; cnt++){if(positionOfStalls[cnt]-lastCowPosition >= testDistance){restCows--;lastCowPosition = positionOfStalls[cnt];}if(restCows == 0)return true;}return false;
}
//找到[L,R]内的最大间隔
long long MinimizeLargestDistance(long long L, long long R){if(IsCurrentDistanceWorks(L)){if(L>=R)return L;}elsereturn 0;if(IsCurrentDistanceWorks((L+R)/2)){long long evenLargerDistance = MinimizeLargestDistance((L+R)/2+1, R);return evenLargerDistance > (L+R)/2 ? evenLargerDistance : (L+R)/2;}elsereturn MinimizeLargestDistance(L, (L+R)/2-1);
}
//归并排序
void Merge(long long ptr_head1, long long ptr_head2, long long ptr_tail){long long ptr1 = ptr_head1, ptr2 = ptr_head2, ptr=0;long long tempSquenceForMerge[ptr_tail-ptr_head1+1];while(ptr1<ptr_head2&&ptr2<=ptr_tail)tempSquenceForMerge[ptr++] = positionOfStalls[ptr1]<positionOfStalls[ptr2]?positionOfStalls[ptr1++]:positionOfStalls[ptr2++];while(ptr1<ptr_head2)tempSquenceForMerge[ptr++] = positionOfStalls[ptr1++];while(ptr2<=ptr_tail)tempSquenceForMerge[ptr++] = positionOfStalls[ptr2++];ptr=0;for(long long cnt=ptr_head1; cnt<=ptr_tail; cnt++)positionOfStalls[cnt]=tempSquenceForMerge[ptr++];
}
void MergeSort(long long ptr_head, long long ptr_tail){if(ptr_head >= ptr_tail) return;MergeSort(ptr_head, (ptr_head+ptr_tail)/2);MergeSort((ptr_head+ptr_tail)/2+1, ptr_tail);Merge(ptr_head, (ptr_head+ptr_tail)/2+1, ptr_tail);
}
//void QuickSort(long long ptr_head, long long ptr_tail){
//	if(ptr_head>=ptr_tail)
//		return;
//	long long ptr1 = ptr_head, ptr2 = ptr_tail;
//	long long timeOfExchanges = 0;
//	long long tempForExchange;
//	while(ptr1 < ptr2){
//		if(positionOfStalls[ptr1] > positionOfStalls[ptr2]){
//			tempForExchange = positionOfStalls[ptr1];
//			positionOfStalls[ptr1] = positionOfStalls[ptr2];
//			positionOfStalls[ptr2] = tempForExchange;
//			timeOfExchanges++;
//		}
//		if(timeOfExchanges%2)
//			ptr1++;
//		else
//			ptr2--;
//	}
//	QuickSort(ptr_head, ptr1-1);
//	QuickSort(ptr1+1, ptr_tail);
//}
int main(){freopen("in.txt", "r", stdin);scanf("%d %d", &N, &C);for(int cnt=0; cnt<N; cnt++)scanf("%d", positionOfStalls+cnt);MergeSort(0, N-1);printf("%d", MinimizeLargestDistance(1, (positionOfStalls[N-1]-positionOfStalls[0])/(C-1)));return 0;
}