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

Re:秀代码的又来了

Posted by helihui at 2009-11-11 07:50:18 on Problem 2231
In Reply To:秀代码的又来了 Posted by:zjut020 at 2008-11-22 22:23:05
这个题目DP 就可以时间复杂在n
#include<stdio.h>
#include<stdlib.h>

int abs(int x)
{
    if(x<0)
        return -x;
    return x;
}

int cmp(void const *a,void const *b)
{
    return (*(int*)a)>(*(int*)b)?1:-1;
}

int main()
{

    __int64 sum,dp;
    int s[10005],t,k,i,c;

    while(scanf("%d",&t)!=EOF)
    {
        sum=dp=c=0;
        for(i=0;i<t;i++)
        {
            scanf("%I64d",&s[i]);
            
        }
        qsort(s,t,sizeof(s[0]),cmp);
        
        for(i=0;i<t;i++)
        {
              
              sum+=(__int64)s[i]*i-(__int64)dp;
              dp+=s[i];
             // printf("dp=%I64d\n",(__int64)s[i]*i);
        }

    
        printf("%I64d\n",sum*2);

        
    }
    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