我的思路就是：先把输入排序，对每两个数字做差，差值为i，数组result[i]保存差值为i的个数，然后对result[i]从i = 0记数，用cnt保存，
如果N为偶数时，则当cnt >= N/2时，输出i,
如果N为奇数，则当cnt > N/2时，输出i
例如:
4
input 1 3 2 4则
result[0] = 0, result[1] = 3, result[2] = 2, result[3] = 1, result[4] = 0, result[5] = 0....以后都是0
遍历数组result,最后输出1
#include<stdio.h>
int cmp(const void *a, const void *b)
{
    return *(int *)b - *(int *)a;
}
int result[500000];
int main()
{
    int N, i, j, k, cnt;
    int *input;
    
    while(scanf("%d",&N) != EOF)
    {
           input = (int *)malloc(N * sizeof(int));
           for(i = 0; i < 500000; i++)
                 result[i] = 0;
           for(i = 0; i < N; i++)
                 scanf("%d",&input[i]);
           qsort(input, N, sizeof(int), cmp);
           for(j = 1; j < N; j++)
                 for(i = 0; i < N - j; i++)
                       result[input[i] - input[i + j]]++;
           cnt = 0;
           for(i = 0; ; i++)
           {
                 cnt += result[i];
                 if(N % 2 == 0 && cnt >= N / 2)
                 {
                      printf("%d\n",i);
                      break;
                 }
                 if(N % 2 != 0 && cnt > N / 2)
                 {
                      printf("%d\n",i);
                      break;
                 }
           }
    }
    system("pause");
    return 0;
}

• 有c(n,2)个差，而不是n个。。 cnt >=n(n-1)/4.. (0) hysramp 2008-04-14 09:16:58
• 再有你那个result[500000]装不下。。且O(n^2)会挂的。。 (0) hysramp 2008-04-14 09:20:49