正题
题目链接:https://www.luogu.com.cn/problem/P7514
题目大意
给出(n)个卡牌有(a_i/b_i)，开始都是(a_i)朝上，将不超过(m)张卡牌变为(b_i)面朝上，使得朝上的数字中最大值减去最小值最小。
(3leq nleq 10^6,1leq m<n,1leq a_i,b_ileq 10^9)
解题思路
虽然数据比较水，但是题目也是一道比较水的贪心题。
先离散化然后考虑暴力点的想法。枚举最大值和最小值(l,r)，那么对于(a_i)在([l,r])之间的自然是不理，在之外的一定需要翻，如果翻转后存在(b_i)不在([l,r])之间，那么显然行不通。
这样我们就可以(O(n^2))了。
不难发现假设([l,r])行的通那么([l,r+1])用原来的方法一定也行得通，所以对于(r)递增，(l)也是不降的，双指针维护一下就好了。
时间复杂度(O(nlog n))
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
using namespace std;
const int N=2e6+10;
int n,m,ans,a[N],b[N],c[N],mx[N],mi[N],nx[N],ni[N],pos[N];
int read(){
int x=0,f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-f;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
bool cmp(int x,int y)
{return a[x]<a[y];}
bool check(int l,int r){
int L=pos[l],R=pos[r+1]-1;
int k=m-(n-R)-(L-1);
if(k<0)return 0;
if(mx[L-1]>r||mi[L-1]<l)return 0;
if(nx[R+1]>r||ni[R+1]<l)return 0;
return 1;
}
int main()
{
n=read();m=read();
for(int i=1;i<=2*n;i++)a[i]=b[i]=read(),c[i]=i;
sort(c+1,c+1+2*n,cmp);int cnt=2*n;
for(int i=1;i<=2*n;i++)a[c[i]]=i;
mi[0]=ni[n+1]=1e9+7;
for(int i=1;i<=n;i++)mx[i]=max(a[i+n],mx[i-1]);
for(int i=1;i<=n;i++)mi[i]=min(a[i+n],mi[i-1]);
for(int i=n;i>=1;i--)nx[i]=max(a[i+n],nx[i+1]);
for(int i=n;i>=1;i--)ni[i]=min(a[i+n],ni[i+1]);
for(int i=1;i<=n;i++)pos[a[i]]=i;pos[cnt+1]=n+1;
for(int i=cnt;i>=1;i--)
if(!pos[i])pos[i]=pos[i+1];
ans=1e9+7;int z=0;
for(int i=1;i<=cnt;i++){
while(z<i&&check(z+1,i))z++;
if(z)ans=min(ans,b[c[i]]-b[c[z]]);
}
printf("%d
",ans);
}