最大值和最小值自然就想到双指针 。
那么就将 $a$ 和 $b$ 数组合并为 $c$ 后排一个序 。
再在 $c$ 上双指针 。
如何判断是否可以在翻不超过 $m$ 次下是所有的牌不超过 $r$ 不小于 $l$ 。
可以枚举一遍如果正面不在范围内就翻，如果翻了还不在就不可能，记录翻的次数 。
这种方法是 $O(n^{2})$ 的 。
然后因为 $a$ 是不下降数列 。
所以翻的一定是左边一段和右边一段 。
二分找到段长 。
再看两段长是否超过 $m$ 。
并且两端中 $b$ 的最大最小值是否超过了范围 。
所以预处理前缀后缀的最大最小 。
复杂度 $O(n\log n)$ 。
复杂度在于二分 。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cctype>
#define int long long
using namespace std;
int n,m;
int a[1000005];
int b[1000005];
int c[2000020];
int big1[1000005],big2[1000005];
int sml1[1000005],sml2[1000005];
int read()
{
char c=getchar();
int x=0;
while(!isdigit(c))c=getchar();
while(isdigit(c))
{
x=x*10+c-'0';
c=getchar();
}
return x;
}
int check(int x,int y)
{
int minn,maxx;
int l=0,r=n+1;
while(l+1<r)
{
int mid=(l+r)/2;
if(a[mid]<x)l=mid;
else r=mid;
}
minn=l;
l=0,r=n+1;
while(l+1<r)
{
int mid=(l+r)/2;
if(a[mid]<=y)l=mid;
else r=mid;
}
maxx=l;
if(n-maxx+minn>m)return 0;
if((big1[minn]>y||sml1[minn]<x)&&minn!=0)return 0;
if((big2[maxx+1]>y||sml2[maxx+1]<x)&&maxx!=n)return 0;
return 1;
}
signed main()
{
int i,j,k;
cin>>n>>m;
a[n+1]=99999999999;
for(i=1;i<=n;i++)cin>>a[i],c[i]=a[i];
for(i=1;i<=n;i++)cin>>b[i],c[i+n]=b[i];
sml1[0]=9999999999;
sml2[n+1]=9999999999;
for(i=1;i<=n;i++)sml1[i]=min(sml1[i-1],b[i]);
for(i=1;i<=n;i++)big1[i]=max(big1[i-1],b[i]);
for(i=n;i>0;i--)sml2[i]=min(sml2[i+1],b[i]);
for(i=n;i>0;i--)big2[i]=max(big2[i+1],b[i]);
sort(c+1,c+2*n+1);
int ans=9999999999;
for(i=1,j=1;i<=2*n,j<=2*n;)
{
if(check(c[i],c[j]))
{
ans=min(c[j]-c[i],ans);
i++;
}
else
{
j++;
}
}
cout<<ans;
return 0;
}
