程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> 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;
}

 

??

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved