专栏文章

题解：P14298 [JOI2023 预选赛 R2] JOI 运动会 / JOI04

封封禁用户
P14298题解参与者 1已保存评论 0

文章操作

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

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

题目大意：

传送门
我们要从 a,b,c,da,b,c,d 数组中各选一个数，使得这 44 个数的最大值与最小值的差最小。
这相当于找到一个最紧凑的四元组。

题目思路：

前提双指针
如果我们确定了 44 个数的最小值，那么为了让差值最小：
  • 我们需要找的其他三个数应该尽可能接近这个最小值。
首先，先排序。
这时候我们就需要用到四个指针 [i,j,k,l][i,j,k,l]，来表示 44 个数组的下标。
那么显然，目前的答案就是：
CPP
int maxn = max({a[i], b[j], c[k], d[l]});//最大值
int minn = min({a[i], b[j], c[k], d[l]});//最小值
mi = min(mi, maxn - minn);//最大值与最小值的差，就是答案
那我们又要如何更新指针呢？
我们这边假设（下标从 11 开始）：
  • a=[1,2,3]a=[1,2,3]
  • b=[4,5,6]b=[4,5,6]
  • c=[7,8,9]c=[7,8,9]
  • d=[10,11,12]d=[10,11,12]
  • i=1,j=1,k=1,l=1i=1,j=1,k=1,l=1
则目前的 maxn⁡=10,minn⁡=1,mi⁡=maxn⁡−minn⁡=10−1=9\operatorname{maxn}=10,\operatorname{minn}=1, \operatorname{mi}=\operatorname{maxn}-\operatorname{minn}=10-1=9。
现在让 l+1l+1，得：
maxn⁡=11,minn⁡=1,mi⁡=maxn⁡−minn⁡=11−1=10\operatorname{maxn}=11,\operatorname{minn}=1, \operatorname{mi}=\operatorname{maxn}-\operatorname{minn}=11-1=10。
我们发现，mi⁡\operatorname{mi} 反而更大了，若现在让 i+1i+1，得：
maxn⁡=10,minn⁡=2,mi⁡=maxn⁡−minn⁡=10−2=8\operatorname{maxn}=10,\operatorname{minn}=2, \operatorname{mi}=\operatorname{maxn}-\operatorname{minn}=10-2=8。
我们发现，mi⁡\operatorname{mi} 变小了，答案更优了，说明每次更新最小值的指针即可。
证明
  • 若更新最小值，mi⁡\operatorname{mi} 显然会变小。
  • 若更新最大值，mi⁡\operatorname{mi} 显然会变大。
  • 若更新中间值，mi⁡\operatorname{mi} 显然不变，没有任何效果。
故，更新最小值最优。
例如：
CPP
if (a[i] == minn) ++i;
else if (b[j] == minn) ++j;
else if (c[k] == minn) ++k;
else ++l;
最后，输出 mi⁡\operatorname{mi} 即可。
最后梳理：
  • 排序：将四个班级的身高数组分别排序。
  • 四指针扫描：使用四个指针分别指向四个数组的当前位置。
  • 贪心策略：每次移动当前最小值所在的指针。
  • 更新答案：记录过程中的最小差值。

代码：

CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 75010;
int n, a[N], b[N], c[N], d[N], mi = 1e9;
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	int i;
	for (i = 1; i <= n; i++) cin >> a[i];
	for (i = 1; i <= n; i++) cin >> b[i];
	for (i = 1; i <= n; i++) cin >> c[i];
	for (i = 1; i <= n; i++) cin >> d[i];
	sort(a + 1, a + 1 + n);
	sort(b + 1, b + 1 + n);
	sort(c + 1, c + 1 + n);
	sort(d + 1, d + 1 + n);
	i = 1;
	int j = 1, k = 1, l = 1;
	while (i <= n && j <= n && k <= n && l <= n) {
		int maxn = max({a[i], b[j], c[k], d[l]});
		int minn = min({a[i], b[j], c[k], d[l]});
		mi = min(mi, maxn - minn);
		if (a[i] == minn) ++i;
		else if (b[j] == minn) ++j;
		else if (c[k] == minn) ++k;
		else ++l;
	}
	cout << mi;
	CODE BY no_coding_extra
	return 0;
}

评论

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

正在加载评论...