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

O(n)(排序O(nlogn))

Posted by 555333444 at 2015-10-17 09:12:19 on Problem 2231
#include <cstdio>
#include <algorithm>
#define MAX_N 10100
typedef long long ll;
using namespace std;
ll N,loc[MAX_N],dp[MAX_N],sum[MAX_N];
int main(){
    scanf("%d",&N);
    for(int i = 1;i <= N;++i){
        scanf("%d",&loc[i]);
    }
    sort(loc + 1,loc + N + 1);
    dp[1] = 0;sum[1] = loc[1];
    for(int i = 2;i <= N;++i){
        dp[i] = dp[i - 1] + (i - 1) * loc[i] - sum[i - 1];
        sum[i] = sum[i - 1] + loc[i];
    }
    printf("%I64d\n",dp[N] * 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