题解：P16830 【MX-X29-T1】『FeOI-6』基站建设 2

Gaoyx · 2026-06-08 11:17:15 · 题解

题目大意

我的理解是扩展 a 数组中每个数的左右端点，使其包含b数组中的所有数，且扩展的长度最小。

题目思路

采用分论讨论的贪心思想（有色线段表示 a 的覆盖范围）：

1. 相邻的两个 a （图中分了三种情况）：

2. 边界的 a ：

代码

实现较劣，建议谨慎参考

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+7;
const int inf = 1e18;
vector <int> e[N];
int n, m, t, c, a[N], b[N], id[N], vis[N];
signed main() {
    cin >> c >> t;
    while(t--) {
        cin >> n >> m;
        for(int i=1;i<=n;i++) {
            cin >> a[i];
        }
        sort(a+1,a+n+1);
        for(int i=1;i<=m;i++) {
            cin >> b[i];
        }
        sort(b+1,b+m+1);
        int tot = 1;
        for(int i=1;i<=m;i++) {
            while(b[i] > a[tot] && tot != n+1) {
                tot++;
            }
            id[i] = tot;
            e[tot].push_back(b[i]);
        }
        long long ans = 0;
        for(int i=1;i<=n+1;i++) {
            int len = e[i].size();
            if(len == 0) continue;
            if(i == 1) {
                ans += abs(e[i][0] - a[1]);
                continue;
            }
            if(i == n+1) {
                ans += abs(e[i][len-1] - a[n]);
                continue;
            }
            int ma = -inf;
            ma = max(abs(e[i][0]-a[i-1]),abs(e[i][len-1]-a[i]));
            for(int j=0;j<len-1;j++) {
                int v = e[i][j];
                int u = e[i][j+1];
                ma = max(ma,u-v);
            }
            ans += (a[i]-a[i-1]-ma);
        }
        cout << ans << "\n";
        for(int i=1;i<=n+1;i++) e[i].clear();
        memset(id,0,sizeof(id));
    }
    return 0;
}