最简单的bsearch，然而我wa了无数次.......最晕的一次是输错数了-_-

ps：两个小循环要全部遍历。因为有可能是14,0,-2,-16这样的情况。

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

int a[1000], n, wi, wj, wk, wu;

int comp(const void *a, const void *b)
{
    int aa = *(int*)a, bb = *(int*)b;
    return aa > bb;
}

int main()
{ 
 //freopen("in.txt", "r", stdin);
 while(scanf("%d", &n) && n)
 {
  int i, k, j, u;
  for(i = 0; i < n; i ++)
   scanf("%d", &a[i]);
  qsort(a, n, sizeof(int), comp);
  wi = 536870912;
  if(n < 4)
   goto out;
  //o(n^3 * logn)
  for(i = n - 1; i >= 0; i --)
  {
   for(k = n - 1; k >= 0; k --)
   {  
    if(i == k) continue;
    for(j = k - 1; j > 0; j --)
    {
     if(j == i) continue;
     u = a[i] - a[k] - a[j];
     if(u != a[i] && u != a[k] && u != a[j])
     {
      //if not equivalent then begin binary search
      int h = n - 1, l = 0, mid;
      while(l <= h)
      {
       mid = (h + l) / 2;
       if(u > a[mid]) l = mid + 1;
       else if(u < a[mid]) h = mid - 1;
       else if(u == a[mid])
       {
        wi = a[i], wk = a[k], wj = a[j], wu = u;
        goto out;
       }      
      }
     }
    }
   }
  }
out: if(wi == 536870912)
   printf("no solution\n");
  else
   //printf("%d %d %d %d\n", wi, wk, wj, wu);
   printf("%d\n", wi);
 }
 return 0;
}

评论