[笔记][中国大学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-smallestPosition}{C-1}]\bigcap Z^{+}$,解空间进一步缩小
本题即是在上述解空间中进行二分查找。

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

1. 递归函数必须强制收缩左右边界，意思是在验证了$\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$，如果不主动收缩左边界，下一次调用区间是不会收缩的，产生死循环。
2. 递归函数在$[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;
} 

出现的问题

在第一次提交的时候，代码中使用的是快速排序，测试样例中有一个例子是77777个隔间位置，而隔间位置都是从小到大输入的。此时如果使用快速排序，理论上会产生77777次递归调用，这肯定会导致溢出。所以改用归并排序后，情况得以解决

这篇关于[笔记][中国大学mooc][程序设计与算法（二） 算法基础][二分算法] 农夫和奶牛的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---