程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> SPOJ 297 Aggressive cows 最小間隔

SPOJ 297 Aggressive cows 最小間隔

編輯：C++入門知識

SPOJ 297 Aggressive cows 最小間隔

題意：給定n個從小到大排好序的數，要從中選出c個數，使得任意兩個相鄰數的間隔最小的值盡量的大。求最大的最小間隔。

最小值最大這樣的問題嘛，當然還是首選二分吧，如果可行的話。顯然這題二分是可以做的。首先我們這樣想。如果取出某c個數中最小的數不是第一個數，那麼我們將它換成第一個數，這樣第一個數和第二個數的間隔不會變小，所以最小的間隔一定不會變小。因此我們選數的時候必選第一個（盡管不是唯一選法，但是選其他的沒有比選第一個能使得最小間隔更大的）。這樣我們二分判斷當前的間隔 x 是否滿足題意。判斷方法很簡單，因為二分固定了間隔值，也就是每兩個數的間隔至少要為 x 。從第一個數開始取，第二個數取離第一個數最近且間隔不小於 x 的數，第三個取離第二個最近的且間隔不小於 x 的數，以此類推，直到不能取數為止，如果取出了不少於 c 個數，那麼該間隔值 x 是可以的。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
using namespace std;

const int MAX = 100005;

int n, c, a[MAX];

bool judge(int x)
{
	int cnt = 1, temp = a[0];
	for(int i = 0; i < n; i++)
	{
		if(a[i] - temp >= x)
		{
			cnt++;
			temp = a[i];
		}
	}
	return cnt >= c;
}

void input()
{
    scanf(%d%d, &n, &c);
    for(int i = 0; i < n; i++)
        scanf(%d, a+i);
}

void solve()
{
    sort(a, a + n);
    int l = 0, r = a[n - 1] - a[0], mid;
    while(l < r)
    {
        mid = (l + r)/2;
        if(judge(mid))
            l = mid + 1;
        else
            r = mid;
    }
    if(!judge(l))
        l--;
    printf(%d
, l);
}

int main()
{
    int T;
	scanf(%d, &T);
	while(T--)
    {
		input();
		solve();
	}

	return 0;
}