UPC11079: 小P的决斗 POJ3244 Difference between Triplets

时间限制: 1 Sec 内存限制: 128 MB
提交: 108 解决: 33
[提交] [状态] [讨论版] [命题人:admin]

题目描述

小P马上就要NOIP了，所以他停课在机房学习。

一天小P在机房和同学交流代码，小P发现他的同学大括号不换行，但是小P的大括号换行。于是他们在争执了大括号是否要换行的问题后决定通过决斗分出胜负。

他们每个人各有三个属性值，ap，ad，生命值。这三个属性可以看成一个三元组:

对于每对三元组Ta=(La,Ja,Ka)，Tb=(Lb,Jb,Kb)，定义Ta,Tb之间的差值D为D(Ta,Tb)=max(La−Lb,Ja−Jb,Ka−Kb)−min(La−Lb,Ja−Jb,Ka−Kb)。

在决斗中，越来越多的对大括号是否要换行持有不同意见的人加了进来，所以决斗变成了团战。

小P想知道为n个人属性值之间两两差值之和，这样他能够知道自己是否能够胜利。

输入

第一行一个整数n。

之后的n行，每行三个整数，表示Li、Ji、Ki。

输出

输出一行，为n个三元组之间两两差值之和（对10^9+7取模）。

样例输入

2
1 2 3
3 2 1

样例输出

提示

对于10%的数据，n≤103；
对于50%的数据，n≤2×104；
对于80%的数据，n≤2×105,1≤Li,Ji,Ki≤107；
对于100%的数据，1≤n≤5×105,1≤Li,Ji,Ki≤108。

假设a<b<c，max(a,b,c)-min(a,b,c) = (c - a + c -a)/2 = (c - b + b - a + c - a)/2 = (|c - b| + |b - a| + |c - a|)/2

因为|c - b| = |b - c|...

所以对于任意大小的 a ,b ,c, max(a,b,c)-min(a,b,c) = (|c - b| + |b - a| + |c - a|)/2

a - b = x1 +x2 -y1 -y2 = x1 - x2 + y1 - y2

所以对每一组数据做差，求出x-y,y-z,z-x,然后排序去掉绝对值

由于是由小到大排序，所以对于第i项，其与前i-1项运算时做被减数，与后n-i项运算时做减数，所以第i项的贡献为a[i]*(i-1)-(n-i)*a[i]。

#include "iostream"
#include "algorithm"
#include "cstdio"

using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int mod = 1e9 + 7;
const int maxn = 5e5 + 100;
ll a[maxn], b[maxn], c[maxn];

ll powmod(ll a, ll b) {
    ll ret = 1;
    while (b) {
        if (b & 1) ret = ret * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ret;
}

int main() {
    freopen("input.txt", "r", stdin);
    int n;

    while (scanf("%d", &n)!=EOF) {
        if (n == 0)
            break;
        ll x, y, z;
        for (int i = 0; i < n; i++) {
            scanf("%lld %lld %lld", &x, &y, &z);
            a[i] = x - y;
            b[i] = y - z;
            c[i] = z - x;
        }
        sort(a, a + n);
        sort(b, b + n);
        sort(c, c + n);
        ll ans = 0;
        for (int i = 0; i < n; i++) {
            ans = (ans + a[i] * i - (n - i - 1) * a[i]) % mod;
            ans = (ans + b[i] * i - (n - i - 1) * b[i]) % mod;
            ans = (ans + c[i] * i - (n - i - 1) * c[i]) % mod;
        }
        printf("%lld
", ans * powmod(2, mod - 2) % mod);
    }
    return 0;
}