我的思路是求 m 次操作一后的数列中,最小的数是答案。
我转化成了求1~m,2~m+1,3~m+2...中的最大值的最小值。但是在Subtask1中WA了几个点,后面特判过了,要怎那么做才不用特判
void mx()
{
h=1,t=0;
for(int i=1;i<=n;i++){
while(h<=t && a[q[t]]<=a[i]) t--;
q[++t]=i;
if(q[h]<i-k+1) h++;
if(i>=k) ans=min(ans,a[q[h]]);
}
}
main()
{
ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
if(n<=5000){
for(int i=1;i<=k;i++){
for(int i=1;i<=n;i++) b[i]=a[i];
for(int i=1;i<n;i++) a[i]=max(b[i],b[i+1]);
n--;
}
sort(a+1,a+1+n);
cout<<a[1];
return 0;
}
mx();
cout<<ans;
return 0;
}