AcWing 420. 火星人
原题链接
中等
作者:
acw_weian
,
2021-01-29 09:57:15
,
所有人可见
,
阅读 481
import java.io.*;
import java.util.*;
class Main{
static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
//从右边开始,找到第一个降序的数字3,
//在3右边的数组里查找到第一个比当前数字3大的数字
//交换两个数字, 然后把3右边的数字按照升序排序
public static void main(String[] args)throws Exception{
int n = Integer.valueOf(read.readLine()), m = Integer.valueOf(read.readLine());
int[] a = new int[n];
String[] ss = read.readLine().split(" ");
for(int i = 0; i < n; i++) a[i] = Integer.valueOf(ss[i]);
for(int i = 0; i < m; i++){
int j = n - 1;
while(j > 0 && a[j - 1] > a[j]) j--;
int l = j, r = n - 1;
while(l < r){
int mid = l + r + 1 >> 1;
if(a[mid] >= a[j - 1]) l = mid;
else r = mid - 1;
}
int tmp = a[l]; a[l] = a[j - 1]; a[j - 1] = tmp;
Arrays.sort(a, j, n);
}
for(int i = 0; i < n; i++) log.write(a[i] + " ");
log.flush();
}
}