CF2149B Unconventional Pairs

Andy1101 · 2025-10-11 22:22:17 · 题解

题目传送门

题目大意

有一个长度为 n 的整数数组（n 是偶数），要将这些数两两配对，恰好分成 \dfrac{n}{2} 对。即 (a_{p_1} , a_{q_1}) , (a_{p_2} , a_{q_2}) , \ \dots \ ,(a_{\frac{p}{2}} , a_{\frac{q}{2}})，且每个下标最多只能属于一对。

对于一对 (x,y)，其差值定义为 \left\vert x-y \right\vert。

需要求出所有配对之中“差值的最大值”的最小值。

思路

如果想要差值的最大值最小，那么就要保证每一对的差值都要小，所以我们可以先排序，将相邻的两个数凑成一对，即 (a_1,a_2) , (a_3,a_4) \ \dots \ (a_{n-1} , a_{n})。然后按照题目要求算出差值的最大值即可。

AC Code：

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int a[N]; 
void solve()
{
    int n;
    cin >>n;
    for(int i=1;i<=n;i++) cin >>a[i];
    sort(a+1,a+n+1);
    int maxx=0;
    for(int i=1;i<=n;i+=2)
    {
        maxx=max(maxx,a[i+1]-a[i]);
    }
    cout <<maxx<<'\n';
}
int main()
{
    int t;
    cin >>t;
    while(t--)
    {
        solve();
    }
    return 0;
}