小蓝与换装大赛
题目 小蓝与换装大赛
思路分析
二分+区间贪心 累了
冲国赛课程里的hard二分题 没几个人写 懒得看了 把题解复制一下
本题主要考察二分+区间贪心
1、首先二分最小能量，\(l=0, r=1e9\)，关键在于二分的 \(check\) 函数
2、我们需要将每件衣服的漂亮值减去当前二分到的最小能量 \(mid\) 转化为区间，因为我们每次换衣所需的能量为 \(|a_i-mid|\)，所以区间范围为 \([a_i-mid, a_i+mid]\)，然后按右端点从小到大排序，把这个问题转化为一个最大不相交区间数量问题。
为什么要这么做呢，我们来看一下样例
样例的所需的最小能量为 2，我们不难发现前 4 件衣服的绝对值范围都存在交集 {3}，此时最小能量 𝐸=𝑚𝑎𝑥(∣1−3∣,∣2−3∣,∣4−3∣,∣5−3∣)=2，所以这 4 件衣服都可以选择漂亮值为 3 的衣服。
剩下两件衣服分别可以选择漂亮值为 32 和 62 的衣服，不影响最后的最小能量 𝐸=𝑚𝑎𝑥(∣1−3∣,∣2−3∣,∣4−3∣,∣5−3∣,∣30−32∣,∣60−62∣)=2
最后预先准备的 3 件衣服漂亮值为 3，32，62。
3、最后比较当前最小能量 \(mid\) 需要预先准备的衣服数量与题目要求需要预先准备的衣服数量的大小，如果需要预先准备的衣服数量大于 \(m\)，说明当前的最小能量 \(E\) 应该要大一些 \(l\) 右移；如果需要预先准备的衣服数量小于 \(m\)，说明最小能量的 𝐸还可以更小。
代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, T, a[N],m;
struct xs {
int l, r;
}t[N];
bool cmp(xs a, xs b) {
return a.r < b.r;
}
bool check(int x) {
for (int i = 1; i <= n; i++) {
t[i].l = a[i] - x;
t[i].r = a[i] + x;
}
sort(t + 1, t + n + 1, cmp);
int ans = 1, f = t[1].r;
for (int i = 2; i <= n; i++) {
if (t[i].l > f) {
f = t[i].r;
ans++;
}
}
return ans <= m;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n>>m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int l = 0, r = 1e9;
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid)) {
r = mid - 1;
} else {
l = mid + 1;
}
}
cout << r + 1 << "\n";
return 0;
}
💬 评论