2017上海金马五校程序设计竞赛 O：An Easy Problem

喜欢ヅ旅行 2022-06-13 23:50 123阅读 0赞

### Problem O : An Easy Problem ###

From: [DHUOJ, 2017060315][DHUOJ_ 2017060315]

Submit (Out of Contest)

Time Limit: 2 s

--------------------

## Description ##

Zhu Ge is a very clever boy. One day, he discovered 2\*n numbers. He wanted to divide them into n groups, each group contains 2 integers, and minimize the sum of the absolute value of the difference of the numbers in each group.  
  
The problem is too difficult to Zhu Ge, so he turned to you. He hopes you can calculate the minimum of the sum of absolute value of the difference among different division strategies.

## Input ##

There are several test cases.  
For each test case, there is an integer n (n < 10,000) at the first line. The second line contains 2\*n integers. The input ends up with EOF.

## Output ##

For each test case, output the minimum of sum.

## Sample Input ##

3
    10 3 4 5 1 6
    5
    64 5 63 63 23 63 54 64 3 54

## Sample Output ##

7
    42

题目意思就是给一个n，然后输入n\*2个数，分成n个组将每组的差的绝对值加起来，让这个值最小，求出这个值。

就是按照大小顺序排序，然后两个两个求出差值加起来就可以了。。

然后错了。。

因为加起来的值不是INT，LONG LONG INT DOUBLE 都可以，改一下救过了呢~\_~

#include<bits/stdc++.h>
    #include<iostream>
    using namespace std;
    int main()
    {
        int n;
        int a[20001];
        while(scanf("%d",&n)!=EOF)
        {
            for(int i=0;i<2*n;i++)
            {
                scanf("%d",&a[i]);
                a[i]=fabs(a[i]);
            }
            sort(a,a+2*n);
            double sum=0;
            for(int i=1;i<=2*n-1;i=i+2)
            {
                sum=sum+a[i]-a[i-1];
            }
            printf("%.0lf\n",sum);
        }
        return 0;
    }

[DHUOJ_ 2017060315]: http://acm.dhu.edu.cn/dhuoj