2993369_ac_122ms_304k.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdlib.h>
#include <stdio.h>

int len, rocks, r;

int rock[200000];

int cmp(const void *p1, const void *p2){
  return(*(int*)p1 - *(int*)p2);
}

int main()
{
int i, a, b, c, p, hits;
  scanf("%d%d%d", &len, &rocks, &r);
  for(i = 0; i < rocks; ++i){
    scanf("%d", &rock[i]);
  }
  qsort(rock,rocks,sizeof(int),cmp);
  a = 0;
  b = len;

  while(a < b){
    c = (a + b + 1) / 2;

    p = 0;
    hits = 0;
    for(i = 0; i < rocks; ++i){
      if(rock[i] - p < c){
	++hits;
      } else {
	p = rock[i];
      }
    }
    if(hits > r){
      b = c-1;
    } else {
      a = c;
    }
  }
  printf("%d\n", a);
  return 0;
}