Lesson 13: MinAbsSumTwo (Min Abs Sum Two)

Lesson 13: MinAbsSumTwo
https://codility.com/programmers/lessons/13

まず配列を昇順にソートします。この時点で最大値が０か負だったり最小値が０か正だった場合は、答えはもうでていますね。

そうでなければ２つのカーソルをつかって配列をチェックしていきましょう。左から右へとすすむものと、右から左へと進むものの 、それぞれlとrと名付けましょう。

もし、lの位置の値がまだ負で絶対値が右のもののより大きければ、lを左へ、逆に右の絶対値が大きければrを左へ、同じならば両方を動かしましょう。

もしlの位置の値が０以上に なったらば、そこで探索をやめることができます。

以下のコードで１００％のスコアになります。

#include <alloca.h> #include <memory.h> #include <math.h> int compare_int(const void *a, const void *b) { //don't do 'return *(int*)a - *(int*)b;', //as it can cause underflow or overflow. if (*(int*)a == *(int*)b){ return 0; } if (*(int*)a < *(int*)b){ return -1; } return 1; } int solution(int A[], int N) { //first we sort in the ascending order qsort(A, N, sizeof(int), compare_int); int l = 0; int r = N - 1; //the initial value for the min int min = abs(A[0] + A[0]); while(l <= r){ int lval = abs(A[l] * 2); int rval = abs(A[r] * 2); int both = abs(A[l] + A[r]); //update the min value if (lval < min){ min = lval; } if (rval < min){ min = rval; } if (both < min){ min = both; } //we A[l] >=0, we have the smallest number already. if (A[l] >= 0){ break; } //move the positions. if (lval < rval){ r--; } else if (lval > rval){ l++; } else { r--; l++; } } return min; }