improve with binary search

diff --git a/07a.c b/07a.c
index 8e3d256..92730a2 100644 (file)
--- a/07a.c
+++ b/07a.c
@@ -3,6 +3,14 @@
 #include <string.h>
 #include <limits.h>
 
+static inline int distance(int crabs[], int ncrabs, int pos)
+{
+       int dist = 0;
+       for (int i = 0; i<ncrabs; i++)
+               dist += abs(crabs[i]-pos);
+       return dist;
+}
+
 int main()
 {
        char *buf = NULL;
@@ -24,13 +32,17 @@ int main()
                ncrabs++;
        }
 
-       int mindist = INT_MAX;
-       for (int i = minp; i<=maxp; i++) {
-               int dist = 0;
-               for (int j = 0; j<ncrabs; j++)
-                       dist += abs(crabs[j]-i);
-               if (dist < mindist)
-                       mindist = dist;
+       int middledist = INT_MAX;
+       int middle = (maxp+minp)/2;
+       while (middle != maxp && middle != minp) {
+               middledist = distance(crabs, ncrabs, middle);
+               if (distance(crabs, ncrabs, middle+1) > middledist) {
+                       maxp = middle;
+                       middle = (middle+minp)/2;
+               } else {
+                       minp = middle;
+                       middle = (middle+maxp)/2;
+               }
        }
-       printf("%d\n", mindist);
+       printf("%d\n", middledist);
 }

diff --git a/07b.c b/07b.c
index a711578..2d361dd 100644 (file)
--- a/07b.c
+++ b/07b.c
@@ -3,6 +3,16 @@
 #include <string.h>
 #include <limits.h>
 
+static inline int distance(int crabs[], int ncrabs, int pos)
+{
+       int dist = 0;
+       for (int i = 0; i<ncrabs; i++) {
+               int d = abs(crabs[i]-pos);
+               dist += (d*d+d)/2;
+       }
+       return dist;
+}
+
 int main()
 {
        char *buf = NULL;
@@ -24,18 +34,17 @@ int main()
                ncrabs++;
        }
 
-       int lastdist = INT_MAX;
-       int dist = INT_MAX;
-       int i = minp;
-       do {
-               lastdist = dist;
-               dist = 0;
-               for (int j = 0; j<ncrabs; j++) {
-                       int d = abs(crabs[j]-i);
-                       for (int k = 1; k<=d; k++)
-                               dist += k;
+       int middledist = INT_MAX;
+       int middle = (maxp+minp)/2;
+       while (middle != maxp && middle != minp) {
+               middledist = distance(crabs, ncrabs, middle);
+               if (distance(crabs, ncrabs, middle+1) > middledist) {
+                       maxp = middle;
+                       middle = (middle+minp)/2;
+               } else {
+                       minp = middle;
+                       middle = (middle+maxp)/2;
                }
-               i++;
-       } while (dist < lastdist);
-       printf("%d\n", lastdist);
+       }
+       printf("%d\n", middledist);
 }