ZYF006 画展布置
ZYF006 画展布置
【算法】 排序、双指针、二分答案
【C++】 sort、双指针、二分答案
【难度】 普及/提高-
一、题目简述
有 幅画,第 幅画的价值为 。展览方要从中选出 幅画按某种顺序布置。定义 为相邻两幅画价值之差的最大值。求 的最小可能值。
输入:第一行两个整数 和 ,第二行 个整数 。
输出:最小的 。
数据范围:,。
简单来说:从 个数里选 个排成一排,让相邻数的差的最大值尽可能小。
二、解题思路
问题分析
首先注意,题目的"按某种顺序布置"意味着我们可以自由安排这 幅画的摆放顺序。为了让相邻差尽量小,显然应该按价值从小到大排列(即排序后依次放置)。
那么问题就变成了:从排序后的 个数中选 个数,使它们排序后相邻差的最大值最小。
关键观察
可以证明:最优方案中,选的 个数在排序后一定是连续的。为什么?假设最优方案选了不连续的一段,比如选了 和 (中间跳过了某些元素)。如果把中间跳过的元素也选上,相邻差只会变小或不变(因为中间的元素介于两端之间,它们填进来会让相邻差更小)。所以选连续的 个数一定不劣。
因此,问题简化为:在排序后的数组中,找一个长度为 的连续子数组,使得子数组内相邻元素差的最大值最小。
方案一:二分答案
二分答案 ,检查是否可行:是否存在长度为 的连续子数组,其中相邻差的最大值 ≤ ?
check(L) 的方法:
- 遍历数组,用贪心找最长的连续段,使得段内相邻差 ≤ 。
- 如果存在某个长度 ≥ 的连续段,则 可行。
因为当一段连续子数组中,任意相邻差 ≤ 时,从中任选 个连续的都能满足条件。
具体实现:
- 从位置 开始,令 (已选第一幅)。
- 对于 到 ,若
a[j] - a[j-1] <= L,则 ++;否则重新开始计数 。 - 途中若 ,返回
true。
二分下界 ,上界 (最大可能差值)。
方案二:排序 + 滑动窗口枚举
枚举每个长度为 的窗口 ,计算窗口内相邻差的最大值,取所有窗口的最小值。
long long ans = LLONG_MAX;
for (int i = 1; i + M - 1 <= N; i++) {
long long maxDiff = 0;
for (int j = i; j < i + M - 1; j++) {
maxDiff = max(maxDiff, a[j+1] - a[j]);
}
ans = min(ans, maxDiff);
}此方法最坏 ,若 较大可能超时。可用二分答案优化。
手动模拟
以 ,价值 [1, 9, 3, 5, 7] 为例。
排序后:[1, 3, 5, 7, 9]
窗口枚举:
- 窗口 [1,3,5]:相邻差 = 2, 2,最大值 = 2
- 窗口 [3,5,7]:相邻差 = 2, 2,最大值 = 2
- 窗口 [5,7,9]:相邻差 = 2, 2,最大值 = 2
最小 。
另一个例子:,价值 [1, 2, 100, 101],排序后窗口:
- 窗口 [1,2]:相邻差 = 1
- 窗口 [2,100]:相邻差 = 98
- 窗口 [100,101]:相邻差 = 1
最小 (选 [1,2] 或 [100,101])。
三、参考代码
方案一:二分答案(推荐,保证不会超时)
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
long long a[N];
int n, m;
// 检查能否选出 M 幅画,使相邻差 ≤ L
bool check(long long L) {
int cnt = 1; // 当前连续段长度
for (int i = 2; i <= n; i++) {
if (a[i] - a[i - 1] <= L) {
cnt++;
if (cnt >= m) return true;
} else {
cnt = 1; // 重新开始
}
}
return cnt >= m;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1);
long long l = 0, r = 2e9, ans = r;
while (l <= r) {
long long mid = (l + r) / 2;
if (check(mid)) {
ans = mid;
r = mid - 1; // 尝试更小的 L
} else {
l = mid + 1;
}
}
cout << ans << endl;
return 0;
}方案二:直接枚举( 较小时可用)
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
long long a[N];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1);
long long ans = LLONG_MAX;
for (int i = 1; i + m - 1 <= n; i++) {
long long maxDiff = 0;
for (int j = i; j < i + m - 1; j++) {
maxDiff = max(maxDiff, a[j + 1] - a[j]);
}
ans = min(ans, maxDiff);
}
cout << ans << endl;
return 0;
}四、复杂度分析
方案一(二分答案):
- 时间复杂度:,其中 为值域范围,。
- 空间复杂度:。
- 这种方案在任何情况下都能稳定通过 的数据。
方案二(直接枚举):
- 时间复杂度:,当 很大时可能超时。
- 空间复杂度:。
易错点
- 二分答案时,
check函数需要精确判断是否存在长度至少为 的连续段,而不是恰好 。 - 二分边界: 初始为
2e9( 最大 ,两个极端值的差最大 )。 - 排序是必须的——不排序就无法用"连续子段"的性质。
