数轴(0 ~ m)上有n个不同点，最多只能移动一个点，移动到[1, m]中任意一点，求最终最小相邻两个点的距离的最大值是什么

题目

思路：先找到相邻距离最小的位置，假设为pos, 那么不是移动第pos个点就是移动第(pos - 1)个点，先移动pos点，用数组vec存除了pos点之外的所有点，求出最小相邻距离和最大相邻距离，那么肯定将pos点插入到最大相邻距离中。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
const int maxn = 1e6 + 5, inf = 1e9 + 5, maxm = 5e3 + 5, mod = 998244353;
int a[maxn];
int n, m;
string s;
int d[maxn];

int calc(vector<int> vec){
    int mn = inf, mx = 0;
    for(int i = 1; i < n; i++){
        mn = min(mn, vec[i] - vec[i - 1] - 1);
        mx = max(mx, vec[i] - vec[i - 1] - 1);
    }
    return min(mn, max((mx - 1) / 2, m - vec[n - 1] - 1));
}

void solve()
{
    cin >> n >> m;
    a[0] = 0;
    int mn = inf, mx = 0;
    int pos;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        d[i] = a[i] - a[i - 1] - 1;
        if(d[i] < mn){
            mn = d[i];
            pos = i;
        }
        // mn = min(mn, d[i]);
        // mx = max(mx, d[i]);
    }
    // cout << mn << ' ' << pos << '\n';
    vector<int> vec;
    for(int i = 0; i <= n; i++){
        if(i == pos) continue;
        vec.pb(a[i]);
    }
    int res = calc(vec);
    if(pos > 1){
        vec[pos - 1] = a[pos];
        res = max(res, calc(vec));
    }
    cout << res << '\n';
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

原文地址：https://blog.csdn.net/way_back__/article/details/135853732

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！