“范式杯”2023牛客暑期多校训练营1 - H - Matches

Solost

2023 年 07 月 19 日

185 次浏览

暂无评论

1760字数

题目题解

## 题目链接

[链接](https://ac.nowcoder.com/acm/contest/57355/H)

## 题目大意

给定两个序列ai,bi,现在可以选择其中一个序列交换其中的两个数字，问经过至多一次操作后最小的|ai - bi|的总和是多少？

## 题解

参考了这篇[题解](https://zhuanlan.zhihu.com/p/644182417)，可以得出我们要想把他减小，那我们必须交换两种不同形式的序列，然后问题就转换成为求若干序列中最长公共序列长度的问题

## 代码

```cpp
#include <algorithm>
#include <array>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#define x first
#define y second
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 2e5 + 10;

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }

ll sum = 0;
    vector<array<int, 3>> seg(n);
    for (int i = 0; i < n; i++) {
        sum += abs(a[i] - b[i]);
        if (a[i] < b[i])
            seg[i] = { a[i], b[i], 0 };
        else
            seg[i] = { b[i], a[i], 1 };
    }
    sort(seg.begin(), seg.end());//按照左端点排序
    int mx[2] = { (int)-2e9, (int)-2e9 };
    ll ans = sum;
    for(auto [l, r, f] : seg){
        auto mxx = mx[f ^ 1];//由之前的推论可得匹配不同类型的才能使得和越小
        if(mxx > l)
            ans = min(ans, sum - 2ll * (min(r, mxx) - l));
        //当前线段的左端点一定要小于下一个线段的左端点，一定是能包裹下一个线段的左端点的，
        //然后最长公共就取决于当前线段的右端点还是已经匹配过线段的最长右端点的差值
        mx[f] = max(r, mx[f]);
    }
    cout << ans << endl;

}
int main()
{
    // IOS;
    int _ = 1;
    // cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}
```

最后修改：2023 年 07 月 19 日