更简洁的阅读体验

题目

给你一个N 个数组成的序列V，要你删除其中K 个数，M 表示剩下的数字中任意两个数的差值的最大值，m 表示最小差值，要你计算删除K 个数后，M+m的最小值。

100 % 100\% 100%的数据 3 ≤ N ≤ 1 , 000 , 000 3\le N\le1,000,000 3≤N≤1,000,000， 1 ≤ K ≤ N − 2 1\le K\le N-2 1≤K≤N−2， − 5 , 000 , 000 ≤ V i ≤ 5 , 000 , 000 -5,000,000\le V_i\le5,000,000 −5,000,000≤Vi​≤5,000,000

题解

这次GDOI有类似的一道题：P7514 卡牌游戏

首先将序列V排序，有个显然的结论是最后留下来的一定是一段连续的长度为 N − K N-K N−K的子序列，证明如下

（V单调不下降）

现有区间为 [ l , r ] [l,r] [l,r]，如果不删去 l − 1 l-1 l−1或者 r + 1 r+1 r+1，而是从 [ l , r ] [l,r] [l,r]中选择一个删去，那么差值的最大值变大，最小值不会变小，因此答案更劣

那么这个题目就简单了，最大差值肯定是序列的首尾两端的差，求最小差值可以用单调队列来做

Code

#include<cstdio>
#include<algorithm>
#define N 1000005
#define ll long long 
#define inf 9999999999999
using namespace std;
struct node
{
	int val,id;
}q[N];
ll n,k,h,t,ans;
ll a[N];
int main()
{
	scanf("%lld%lld",&n,&k);k=n-k;
	for (int i=1;i<=n;++i)
		scanf("%lld",&a[i]);
	sort(a+1,a+n+1);
	h=1;t=0;
	a[0]=-inf;ans=inf;
	for (int i=2;i<k;++i)
	{
		while (h<=t&&q[t].val>=a[i]-a[i-1]) --t;
		q[++t].val=a[i]-a[i-1];q[t].id=i;
	}
	for (int i=k;i<=n;++i)
	{
		while (h<=t&&q[t].val>=a[i]-a[i-1]) --t;
		q[++t].val=a[i]-a[i-1];q[t].id=i;
		while (h<=t&&q[h].id+k<=i) ++h;
		ans=min(ans,q[h].val+a[i]-a[i-k+1]);
	}
	printf("%lld\n",ans);
	return 0;
}