Algoogle

Algorithm for Programming Contest

PKU 2231 Moo Volume

Category: PKU Tag: math

Moo Volume

問題概要


解法


愚直にN*(N-1)調べるのは明らかにあれなので式を立てます.
牛のいる場所を小さい順にd0, d1, … , dN-1 とする.
diとの距離の差を出すときに di より大きい場所となら -di, そうでないなら +di する.
各 d は 他の各 d についてそれぞれ2回計算し, di 以上の数は N-i-1 個, di 以下の数は i個
よって各 di について
-2*(N-1-i) *di + 2*i*di
して足せばよい.
入力のサイズ的にintではオーバーフローするので注意.

コード


(2231.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <algorithm>
#include <cstdio>

using namespace std;

#define int long long

int N;
int d[10010];

signed main(){
    scanf("%lld", &N);
    for(int i = 0; i < N; i++)
        scanf("%lld", d+i);
    sort(d, d+N);

    int ans = 0;
    for(int i = 0; i < N; i++)
        ans += (-2*(N-1-i) + 2*i) * d[i];
    printf("%lld\n", ans);
    return 0;
}

Comments