二元矩陣峰值搜索

A farmer has built a long barn with N stalls. The stalls are placed in a straight manner at positions from x1, x2, ...xN. But his cows (C) are aggressive and don’t want to be near other cows. To prevent cows from hurting each other, he wants to place them in such a way so that the minimum distance between them is as large as possible. What is the largest minimum distance?

一位農民用N個攤位建造了一個長谷倉。 檔位以直線方式放置在x1，x2，... xN處 。 但是他的母牛(C)具有攻擊性，不想靠近其他母牛。 為了防止母牛互相傷害，他想以這樣的方式放置它們，使它們之間的最小距離盡可能大。 最大最小距離是多少？

Constraints:

限制條件：

N: 2<=N<=100,000C: 2<=C<=NXi: 0<=Xi<=1,000,000,000

Input:

輸入：

Line1: Two integers N and CNext N lines: An integer for Xi stall's position

Example:

例：

Input: 5 31 2 4 8 9Output:3

Explanation:

說明：

If the cows are placed at 1,4 and 9, it will result in minimum distance from 3.

如果將母牛放在1,4和9處，則距離3的距離最小。

SOLUTION AND CODE

解決方案和代碼

Since the range of xi is from 0 to 10^9, one can say that the minimum distance between the cows will lie between the range. The minimum distance between 2 stalls can be 0 (lower bound) and maximum distance is 10^9 (upper bound). So, one can check for each value from lower bound to upper bound.

由于xi的范圍是0到10 ^ 9，因此可以說母牛之間的最小距離將介于該范圍之間。 2個檔位之間的最小距離可以為0(下限)，最大距離為10 ^ 9(上限)。 因此，可以檢查從下限到上限的每個值。

Let's say for k minimum distance, we can check if it is possible to place cows in the stall. In case, you have reached the last stall but didn’t have placed all cows, then it is not possible else it is possible.

假設有k個最小距離，我們可以檢查是否可以將奶牛放在攤位中。 萬一您到達了最后一個攤位，但沒有放完所有母牛，那么就不可能了。

A point to note is that if, for a k, it is possible to place the cows. Then all the values less than k will be true. Also, if k is false, then all the values greater than k will be false. We can say it is creating a monotonic function and we have to check for the transition from true to false and return that value.

需要注意的一點是，如果以ak為單位，則可以放置母牛。 那么所有小于k的值都將為真。 同樣，如果k為假，則所有大于k的值都為假。 我們可以說它正在創建一個單調函數，我們必須檢查從true到false的轉換并返回該值。

It can be quickly and easily done with Binary Search from the range of 0 to 10^9.

使用Binary Search可以從0到10 ^ 9的范圍內快速輕松地完成此操作。

CODE

碼

#include <bits/stdc++.h> using namespace std;int N,C;int check(int num,int stalls[]) {int cows=1,pos=stalls[0];for (int i=1; i<N; i++){if (stalls[i]-pos>=num){pos=stalls[i];cows++;if (cows==C)return 1;}}return 0; }int binarySearch(int stalls[]) {int start=0,end=stalls[N-1],max=-1;while (end>start){int mid=(start+end)/2;if (check(mid,stalls)==1){if (mid>max)max=mid;start=mid+1;}elseend=mid;}return max; }int main() {int t;cin>>t;while (t--){cin>>N>>C;int stalls[N];for (int i=0; i<N; i++)cin>>stalls[i];sort(stalls,stalls+N);int k=binarySearch(stalls);cout<<k;}return 0; }

Output

輸出量

翻譯自: https://www.includehelp.com/data-structure-tutorial/aggressive-cows-on-binary-search.aspx

二元矩陣峰值搜索

總結

以上是生活随笔為你收集整理的二元矩阵峰值搜索_好斗的牛（二元搜索）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。