专栏文章

CF2149B Unconventional Pairs

AAndy1101
CF2149B题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minmr6l3
此快照首次捕获于
2025/12/02 04:57
3 个月前
此快照最后确认于
2025/12/02 04:57
3 个月前
查看原文

题目传送门

题目大意

有一个长度为 nn 的整数数组（nn 是偶数），要将这些数两两配对，恰好分成 n2\dfrac{n}{2} 对。即 (ap1,aq1),(ap2,aq2), … ,(ap2,aq2)(a_{p_1} , a_{q_1}) , (a_{p_2} , a_{q_2}) , \ \dots \ ,(a_{\frac{p}{2}} , a_{\frac{q}{2}})，且每个下标最多只能属于一对。
对于一对 (x,y)(x,y)，其差值定义为 ∣x−y∣\left\vert x-y \right\vert。
需要求出所有配对之中“差值的最大值”的最小值。

思路

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

AC Code：

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...