每日算法：洛谷U535992 J-C 小梦的宝石收集（双指针、二分）

题目描述

小梦有 n 颗能量宝石，其中第 i 颗的能量为 ai​，但这些能量宝石十分不稳定，随时有可能发生崩坏，导致他们全部消失！

小梦想要留住宝石们，不希望他们发生崩坏，同时他发现：如果这些宝石的能量的极差越大，则这些宝石们越不稳定，因此他希望最小化这些宝石的能量的极差（最大值减去最小值的差值）。

小梦有一招点石成金的技能，这个技能可以以如下方式改变一些宝石的能量：

∙ 要么小梦选择一块能量最小的宝石，将他变成一块当前能量最大的宝石。

∙ 要么小梦选择一块能量最大的宝石，将他变成一块当前能量最小的宝石。

形式化的即：

∙ 选择 i (1≤i≤n,ai​=min(a1​,a2​,...,an​))，执行：ai​:=max(a1​,a2​,...,an​)。

∙ 或选择 i (1≤i≤n,ai​=max(a1​,a2​,...,an​))，执行：ai​:=min(a1​,a2​,...,an​)。

小梦至多可以使用 k 次上述的 ”点石成金“ 技能，他想知道这些宝石的能量极差最小可以变为多少，请你帮他算一算吧。

输入格式

本题有多组测试数据。

输入的第一行包含一个正整数 T，表示数据组数。

接下来包含 T 组数据，每组数据的格式如下：

第一行两个正整数 n,k，分别表示小梦拥有的宝石数量 n ，和他最多可以释放 “点石成金” 技能的次数 k。

第二行 n 个正整数 ai​，表示每块宝石的能量。

输出格式

对于每组测试数据：

在单独的一行输出一个整数，表示宝石能量的极差最小值。

输入输出样例

输入 #1

2
8 3
1 2 3 4 5 6 7 8
4 3
100 1 100 2

输出 #1

4
0

说明/提示

【样例 1 解释】

使用 3 次操作一，选择 min 变为 max，操作完后数组变成：{8,8,8,4,5,6,7,8}。

此时数组的极差为 4 最小，可以证明不存在比 4 更优的答案。

【数据范围】

令 N 表示 T 组数据中 n 的总和。

对于 30% 的数据有：T=1,1≤k≤N≤20。

对于 60% 的数据有：1≤T≤10,1≤k≤N≤2000。

对于所有的测试数据有： 1≤T≤1000,1≤N≤5×105,0≤k≤n,0≤ai​≤109。

思路：

我们很容易想到，先将数组进行排序，然后分别用两个指针l，和r表示最左侧的最大值和最右侧的最小值。

 每次只要有将最小值变成最大值或者将最大值变成最小值的情况出现，那么我们就需要移动左或右指针到次小或次大值的位置上。

这样，我们假设当l指针在i位置，r指针在j位置时，找到答案，则操作次数为：（i-1）【操作左边要用的次数】+（n-j）【操作右边要用的次数】+min(i-1,n-j)【将左边的值变成最大值或将右边的值变为最小值后，额外再需要移动的次数 例：如果左边是1，右边是8，修改左边后，最后面的两个数应该是8,8因此如果此时要再操作右边，应该额外加上左边的操作次数，同理另一种情况也是如此，而这个值我们希望它尽可能小，这样可操作的次数就会变多】

而由题目规定，我们可知：（i-1）+（n-j）+min(i-1,n-j) <= k

因此当符合这一规定时，我们 则用ans记录它的差值，取最小值。

于是我们可以很轻松的想到双重循环遍历枚举，但是双重循环肯定过不了，然后我们发现:该数组中的数是单调递增的，且满足二分性，因此我们可以将第二重循环优化为二分，这样的时间复杂度是nlogn。

代码：

#include<bits/stdc++.h>using namespace std;
int t,n,k;
const int N = 5e5+10;
int q[N];int main(){cin>>t;while(t--){cin>>n>>k;for(int i =1;i<=n;i++){cin>>q[i];}sort(q+1,q+n+1);//先从小到大排序 int ans = INT_MAX;//初始化为极大值 for(int i = 1;i<=n;i++){if(i - 1 > k) break;int l = i,r = n;//在从i到n的区间里找到右边界 if(i - 1>k) break;//操作次数超过k了，直接跳出 while(l <= r){int mid = (l+r) / 2;if((i-1) + (n - mid) + min(i-1,n-mid) <= k) r = mid-1;else l = mid+1;}ans = min(ans,q[l]-q[i]);//每次更新取最小值 }cout<<ans<<endl;}return 0;
}