07a.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4 #include <limits.h>
   5
   6 static inline int distance(int crabs[], int ncrabs, int pos)
   7 {
   8         int dist = 0;
   9         for (int i = 0; i<ncrabs; i++)
  10                 dist += abs(crabs[i]-pos);
  11         return dist;
  12 }
  13
  14 int main()
  15 {
  16         char *buf = NULL;
  17         size_t len = 0;
  18         int crabs[1000] = {0};
  19         int ncrabs = 0;
  20         int maxp = 0;
  21         int minp = INT_MAX;
  22
  23         getline(&buf, &len, stdin);
  24         char *p = strtok(buf, ",");
  25         crabs[ncrabs] = atoi(p);
  26         maxp = crabs[ncrabs];
  27         minp = crabs[ncrabs++];
  28         while ((p = strtok(NULL, ",")) != NULL) {
  29                 crabs[ncrabs] = atoi(p);
  30                 maxp = maxp < crabs[ncrabs] ? crabs[ncrabs] : maxp;
  31                 minp = minp > crabs[ncrabs] ? crabs[ncrabs] : minp;
  32                 ncrabs++;
  33         }
  34
  35         int middledist = INT_MAX;
  36         int middle = (maxp+minp)/2;
  37         while (middle != maxp && middle != minp) {
  38                 middledist = distance(crabs, ncrabs, middle);
  39                 if (distance(crabs, ncrabs, middle+1) > middledist) {
  40                         maxp = middle;
  41                         middle = (middle+minp)/2;
  42                 } else {
  43                         minp = middle;
  44                         middle = (middle+maxp)/2;
  45                 }
  46         }
  47         printf("%d\n", middledist);
  48 }