题目描述
输入 $n,k(1≤k≤n≤3e5)$ 和长为 $n$ 的数组 $a(1≤a[i]≤1e9)$。
把这 $n$ 个数重新排列,然后分成若干个组,要求每组至少有 $k$ 个数。
定义 $diff(b)$ 表示序列 $b$ 中最大值与最小值的差。
计算所有组的 $diff$ 值的最大值 $mx$。
输出 $mx$ 的最小值。
样例
输入样例1
5 2
50 110 130 40 120
输出样例1
20
输入样例2
4 1
2 3 4 1
输出样例2
0
算法1
(二分+dp+双指针) $O(n*log(n))$
我们可以二分答案。可以证明答案具有二段性,如果当前答案不行时,表示我们无法最优分组,使得每组的差值的最大值小于等于当前数,那么当答案再小时,也是肯定不行的,所以答案一定在右边。
下面我们需要考虑怎样每次去检查当前mid是否满足。且只能在时间复杂度o(n)的范围内检查,等于说只能循环一遍,但是分组又有很多种情况要考虑,而dp就可以满足这个要求,时间复杂度低,且可以考虑到所有情况。我们用f[i]表示从1到i是否满足,设当前枚举的左端点为j(j<=i-k+1),那么让f[i]满足的条件是f[j-1]满足并且w[i]-w[j]<=mid,那我们在考虑f[i+1]时,设满足f[i]的左端点为j,考虑两种情况,一种是w[i+1]-w[j]<=mid,那么f[i+1]也满足条件;第二种情况是w[i+1]-w[j]>mid,那么可以满足f[i+1]的左端点一定在j的右边。由此看来,我们可以用双指针去维护这一性质。dp+双指针,时间复杂度为o(n);
C++ 代码
#include<bits/stdc++.h>
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;
const int N = 3e5+10, M = N * 2, INF = 2e9;
int n, k;
int w[N], f[N];
bool check(int mid)
{
memset(f, 0, sizeof f);
f[0] = 1;
for(int i=k,j=1;i<=n;i++)
{
while(j<=i-k+1){
if(f[j-1] && w[i]-w[j]<=mid){
f[i] = j;
break;
}
j++;
}
}
return f[n];
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>w[i];
sort(w+1,w+n+1);
int l=0,r=1e9;
while(l<r){
int mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
cout<<r<<endl;
return 0;
}