題目描述

小夢有?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;
}