11397: 【原1397】数学题2

题目

题目描述

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

题目描述

给定n个正整数，请问它们两两之间的绝对值之差的和为多少？

例如：给定4个正整数1, 5, 2, 3，结果为

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

输入格式

测试数据包含2行。

第一行为一个正整数n。

第二行有n个正整数，每个正整数不大于1000000。

输出格式

结果为一行正整数，代表求出的和对1000000007取模的结果。

Sample Input

4
1 5 2 3

Sample Output

13

说明

对于60%的数据，1 <= n <= 50000；对于100%的数据1 <= n <= 100000。

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() {
    n = read();
    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;
}