SPOJ 297 Aggressive cows 最小间隔 - c++编程基础

TOP

SPOJ 297 Aggressive cows 最小间隔

2015-11-21 00:57:18 来源: 作者: 【大中小】浏览:2次

题意：给定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; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：[LeetCode][Java] First Missing ..	下一篇：[LeetCode][Java] Trapping Rain ..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: