# 11397: 【原1397】数学题2

### 题目描述

author: SamJia 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1397

## 题目描述

|1-5| + |1-2| + |1-3| + |5-2| + |5-3| + |2-3| = 13

## Sample Input

``````4
1 5 2 3
``````

## Sample Output

``````13
``````

## q4x3's solution

``````/**
* 数学题
* 排个序就清楚了
* long long
**/
#include <iostream>

using namespace std;

template <typename T>
void merge(int lo, int mi, int hi, T* a)
{
T* A = a + lo;
int lb = mi - lo;
T* B = new T[lb];
T* BB = B;
for(int i = 0;i < lb;++ i)
B[i] = A[i];
int lc = hi - mi;
T* C = a + mi;
int cnt = 0;
while(1) {
if ((lb == 0) && (lc == 0)) break;
if (lb == 0) {
A[cnt] = C[0];
++ cnt; ++ C; -- lc;
}
else if (lc == 0) {
A[cnt] = B[0];
++ cnt; ++ B; --lb;
}
else {
if(B[0] < C[0]) {
A[cnt] = B[0];
++ cnt; ++ B; -- lb;
}
else {
A[cnt] = C[0];
++ cnt; ++ C; -- lc;
}
}
}
delete []BB;
}

template <typename T>
void mergeSort(int lo, int hi, T* A)
{
if(hi - lo < 2) return;
int mi = (lo + hi) / 2;
mergeSort(lo, mi, A); mergeSort(mi, hi, A);
merge(lo, mi, hi, A);
}

long long n, _n, a[100233], ans, cnt;

int main() {
cin >> n;
_n = n;
for(int i = 0;i < n;++ i)
cin >> a[i];
mergeSort(0, n, a);
-- _n;
while(_n > 0) {
ans += ((_n % 1000000007) * (a[n - 1 - cnt] - a[cnt]) % 1000000007);
ans %= 1000000007;
_n -= 2;
++ cnt;
}
cout << ans << endl;
}
``````

## victrid's solution

``````#include <cstring>
#include <iostream>
using namespace std;
int* MergeSort(int* list, int listSize) {
if (listSize == 1)
return list;
if (listSize == 2) {
if (list[0] > list[1]) {
int temp = list[0];
list[0]  = list[1];
list[1]  = temp;
return list;
}
return list;
}
int* tmplist = new int[listSize];
int* llst    = MergeSort(list, listSize / 2);
int* rlst    = MergeSort(list + listSize / 2, listSize - listSize / 2);
int lct = 0, rct = 0;
while (lct + rct != listSize) {
if ((llst[lct] <= rlst[rct] && lct < listSize / 2) || rct >= listSize - listSize / 2) {
tmplist[lct + rct] = llst[lct];
lct++;
} else {
tmplist[lct + rct] = rlst[rct];
rct++;
}
}
memcpy(list, tmplist, sizeof(int) * listSize);
delete[] tmplist;
return list;
}
int main() {
int n;
cin >> n;
int* l1 = new int[n];
for (int i = 0; i < n; i++)
scanf("%d", &l1[i]);
MergeSort(l1, n);
long long ans = 0;
int lf, rf;
if (n % 2) {
lf = n / 2;
rf = n / 2;
} else {
lf = n / 2 - 1;
rf = n / 2;
}
while (lf != -1) {
//! the digits' problem
ans += (long long)(rf - lf) * (long long)(l1[rf] - l1[lf]);
lf--;
rf++;
//need to be moded
ans %= 1000000007;
}
cout << ans;
return 0;
}
``````

## yyong119's solution

``````#include <cstdio>
#include <algorithm>
#define MAX_N 100005
using namespace std;
const int MOD = 1000000007;
int n, ans, p, q;
int a[MAX_N];
inline int read() {
char ch = getchar(); int flag = 1, res = 0;
while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if (ch == '-') flag = -1, ch = getchar();
while (ch >= '0' && ch <= '9')
res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
return res * flag;
}
int main() {
for (register int i = 0; i < n; ++i) a[i] = read();
/*
6个数有5个间隔，每个间隔分别被计算了
1*5, 2*4, 3*3, 4*2, 5*1次
下面的a[i]被更新为delta值，p, q分别是两个倍率
*/
sort(a, a + n);
for (register int i = 0; i < n; ++i) a[i] = a[i + 1] - a[i];
p = 0, q = n;
for (register int i = 0; i < n - 1; ++i) {
++p; --q;
// 注: p, q, cur_ratio, ans直接用long long循环内只MOD一次会WA
int cur_ratio = (long long)p * q % MOD;
ans += (long long)cur_ratio * a[i] % MOD;
ans %= MOD;
}
printf("%d\n", ans);
return 0;
}
``````