Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

总是WA,为什么呀?

Posted by xuanbao at 2008-04-13 22:38:44 on Problem 3579 and last updated at 2008-04-13 22:39:48
我的思路就是:先把输入排序,对每两个数字做差,差值为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;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator