AcWing 420. 火星人
原题链接
中等
作者:
季之秋
,
2021-02-22 18:14:50
,
所有人可见
,
阅读 153
/*
画坐标轴我们发现规律:全单调递增是最大值,全单调递减是最小值,
肯定从最小位开始改,改不了就一直找,直到第k位
每次找到第k位,我们将k改成稍微大一点的值,如果找k位前的值i交换会导致i位变大,
而我们肉眼观察到变大i会错过很多次中间的变换,所以从后面开始找,接着交换之后k位后面的值
k后面的数就可以从最小值开始
因为找的时候k前面是单调递增,所以反转一下就变成单调递减-->最小值
*/
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
int w[]=new int[n+10];
for(int i=1;i<=n;i++){
w[i]=sc.nextInt();
}
while(m--!=0){
int k=n;
while(w[k-1]>w[k]) k--;
int t=k;
while(w[t+1]>w[k-1]) t++;
w=swap(w,t,k-1);
w=reverse(w,k,n);
}
for(int i=1;i<=n;i++)
System.out.print(w[i]+" ");
}
static int[] swap(int arr[],int a,int b){
int c=arr[a];
arr[a]=arr[b];
arr[b]=c;
return arr;
}
static int[] reverse(int arr[],int l,int r){
while(true){
arr=swap(arr,l,r);
l++;r--;
if(l>(l+r)/2) return arr;
}
}
}