[JZOJ3154]「提高A组模拟」『单调队列』删数字

题解 单调队列

题目

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

$100\%$的数据 $3\le N\le1,000,000$，$1\le K\le N-2$，$-5,000,000\le V_i\le5,000,000$

题解

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

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

（V单调不下降）

现有区间为$[l,r]$，如果不删去$l-1$或者$r+1$，而是从$[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;
}