练习题 - 进击的奶牛(数理逻辑)

前言

算法拾遗继续。

题目

问题描述

Farmer John建造了一个有N(2<=N<=100,000)个隔间的牛棚,这些隔间分布在一条直线上,坐标是x1,...,xN (0<=xi<=1,000,000,000)。

他的C(2<=C<=N)头牛不满于隔间的位置分布,它们为牛棚里其他的牛的存在而愤怒。为了防止牛之间的互相打斗,Farmer John想把这些牛安置在指定的隔间,所有牛中相邻两头的最近距离越大越好。那么,这个最大的最近距离是多少呢?

输入(aggr.in)

第1行:两个用空格隔开的数字N和C。  
第2~N+1行:每行一个整数,表示每个隔间的坐标。

输出(aggr.out)

输出只有一行,即相邻两头牛最大的最近距离。

样例

aggr.in

5 3
1 
2 
8 
4 
9

aggr.out

3

解答

该题为普及组的题目,因此难度并不大。解题思路为二分枚举(1,(max(a[i]) - min(a[i])) / (c - 1))中的取值,具体代码实现如下。

#include <stdio.h>

int n, c, a[100002] = {0}, b[100002] = {0};

void kuaipai(int first, int end, int x[]) {
  if (first >= end)
    return;
  else {
    int mid = (first + end) / 2, num;
    num = x[mid];
    x[mid] = x[first];
    int i = first, j = end;
    while (i < j) {
      while (i < j && x[j] > num)
        j--;
      if (i < j) {
        x[i] = x[j];
        i++;
      }
      while (i < j && x[i] <= num)
        i++;
      if (i < j) {
        x[j] = x[i];
        j--;
      }
    }
    x[i] = num;
    kuaipai(first, i - 1, a);
    kuaipai(i + 1, end, a);
  }
}

int cmp(const void *x, const void *y) { return *(int *)x - *(int *)y; }

int can(int num) {
  int tot = 0;
  int di = a[1];
  int i;
  for (i = 2; i <= n; i++)
    if (a[i] >= di + num) {
      tot++;
      di = a[i];
    }
  if (tot >= c - 1)
    return 1;
  return 0;
}

int main() {
  scanf("%d%d", &n, &c);
  int i;
  for (i = 1; i <= n; i++)
    scanf("%d", &a[i]);

  kuaipai(1, n, a);

  int left = 0, right = (a[n] - a[1]) / (c - 1), mid;
  while (left <= right) {
    mid = (left + right) / 2;
    if (can(mid))
      left = mid + 1;
    else
      right = mid - 1;
  }
  printf("%d\n", right);

  return 0;
}

在洛谷上测试,通过率100%。

参考


* cached version, generated at 2018-12-02 14:17:20 UTC.

Subscribe by RSS