07b.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                 int d = abs(crabs[i]-pos);
  11                 dist += (d*d+d)/2;
  12         }
  13         return dist;
  14 }
  15
  16 int main()
  17 {
  18         char *buf = NULL;
  19         size_t len = 0;
  20         int crabs[1000] = {0};
  21         int ncrabs = 0;
  22         int maxp = 0;
  23         int minp = INT_MAX;
  24
  25         getline(&buf, &len, stdin);
  26         char *p = strtok(buf, ",");
  27         crabs[ncrabs] = atoi(p);
  28         maxp = crabs[ncrabs];
  29         minp = crabs[ncrabs++];
  30         while ((p = strtok(NULL, ",")) != NULL) {
  31                 crabs[ncrabs] = atoi(p);
  32                 maxp = maxp < crabs[ncrabs] ? crabs[ncrabs] : maxp;
  33                 minp = minp > crabs[ncrabs] ? crabs[ncrabs] : minp;
  34                 ncrabs++;
  35         }
  36
  37         int middledist = INT_MAX;
  38         int middle = (maxp+minp)/2;
  39         while (middle != maxp && middle != minp) {
  40                 middledist = distance(crabs, ncrabs, middle);
  41                 if (distance(crabs, ncrabs, middle+1) > middledist) {
  42                         maxp = middle;
  43                         middle = (middle+minp)/2;
  44                 } else {
  45                         minp = middle;
  46                         middle = (middle+maxp)/2;
  47                 }
  48         }
  49         printf("%d\n", middledist);
  50 }