Skip to content

11598: 【原1598】Matching

题目

题目描述

author: Online Judge 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1598

Description

Given two sequence lists A={a[1],a[2],…,a[n]},B={b[1],b[2],…,b[n]}, find n elements from A and B to construct one-to-one pair respectively, we want to maximize the sum of absolute differences between each element and its pair.

Note:

  • Every element from A and B should be considered.
  • Using repeated element is NOT allowed.
  • Each element from A and B has to be positive integer.
  • Every element would not exceed 10000.
  • n would never exceed 3000

Sample Input

4
2 5 6 3
1 4 6 7

Sample Output

14

ligongzzz's solution

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;
    vector<int> vdata(2 * n);

    for (int i = 0; i < 2 * n; ++i)
        cin >> vdata[i];
    sort(vdata.begin(), vdata.end());

    int ans = 0;
    for (int i = 0; i < n; ++i) {
        ans -= vdata[i];
    }
    for (int i = n; i < 2 * n; ++i) {
        ans += vdata[i];
    }

    cout << ans;

    return 0;
}