B. Teams Forming

2018-12-19 00:44:59


题目链接:

https://codeforces.com/contest/1092/problem/B

原题:

Problem Statement

There are n students in a university. The number of students is even. The i-th student has programming skill equal to ai.

The coach wants to form n2 teams. Each team should consist of exactly two students, and each student should belong to exactly one team. Two students can form a team only if their skills are equal (otherwise they cannot understand each other and cannot form a team).

Students can solve problems to increase their skill. One solved problem increases the skill by one.

The coach wants to know the minimum total number of problems students should solve to form exactly n2 teams (i.e. each pair of students should form a team). Your task is to find this number.

Input

The first line of the input contains one integer n (2≤n≤100) — the number of students. It is guaranteed that n is even.

The second line of the input contains n integers a1,a2,…,an (1≤ai≤100), where ai is the skill of the i-th student.

Output

Print one number — the minimum total number of problems students should solve to form exactly n2 teams.

Examples

input1

6
5 10 2 3 14 5

output1

5

input2

2
1 100

output2

99

Note

In the first example the optimal teams will be: (3,4), (1,6) and (2,5), where numbers in brackets are indices of students. Then, to form the first team the third student should solve 1 problem, to form the second team nobody needs to solve problems and to form the third team the second student should solve 4 problems so the answer is 1+4=5.

In the second example the first student should solve 99 problems to form a team with the second one.


题意:

简单来说,就是让n个数两两相等,能够增加某个数的值,求最小的使全体两两相等的增加值总和。

思路:

有相等的数时可以将两个数忽略,其他的用第i-1大的数减去第i大的结果,相加就是最小使全体两两相等的增加值总和。

AC代码:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
typedef long long ll;
#include<vector>
#define cin(n) scanf("%lld",&(n))
#define cout(n) printf("%lld",(n))
#define couc(c) printf("%c",(c))
#define coutn printf("\n")
#define cout_ printf(" ")
#define debug() printf("haha\n")
ll t,n,k;
ll a[105];
int main()
{
    cin(n);
    for(int i=1;i<=n;i++)
    {
        ll p;
        cin(p);
        a[p]++;
        a[p]%=2;
    }
    ll ans=0,num=0;
    for(int i=1;i<=100;i++)
    {
        if(a[i])
        {
            if(num==0)
            {
              num=i;
            }
            else
            {
                ans+=i-num;
                num=0;
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}