题解 | 小红的双排列权值

#include<bits/stdc++.h>
using namespace std;
/*此代码的逻辑是先记录每个重复数字的位置，第一次出现的存在first[k]里面，
第二次出现存在second[k]里面，再从最first[k]里面找出最大的与second[k]里面最小的互换
最终权值 = 初始基础权值 + 互换后的最大增量；再输出这个值；
*/
int main() {
    int n;
    cin >> n;
    vector<int> a(2 * n);
    for (int i = 0; i < 2 * n; ++i) {
        cin >> a[i];
    }

    vector<int> first(n + 1, 0), second(n + 1, 0);
    for (int i = 0; i < 2 * n; ++i) {
        int num = a[i];
        if (first[num] == 0) {
            first[num] = i + 1; // 位置从1开始计数
        } else {
            second[num] = i + 1;
        }
    }

    long long base = 0;
    for (int k = 1; k <= n; ++k) {
        base += second[k] - first[k] - 1;
    }

    int max_first = 0, min_second = INT_MAX;
    for (int k = 1; k <= n; ++k) {
        max_first = max(max_first, first[k]);
        min_second = min(min_second, second[k]);
    }

    long long max_delta = max(0LL, 2LL * (max_first - min_second));

    cout << base + max_delta << endl;

    return 0;
}