1529: 寻找最大数

Time Limit: 1 Sec  

Memory Limit: 128 MB

Submit: 107  

Solved: 53

Description

给出一个整数n每次可以移动相邻数位上的数字，最多移动k次，得到一个新的整数，求这个新的整数的最大值是多少。

Input

多组测试数据。

每组测试数据占一行，每行有两个数N和K (1 ≤ N≤ 10^100; 0 ≤ K ≤ 100).

Output

每组测试数据的输出占一行，输出移动后得到的新的整数的最大值。

Sample Input

1990 1

100 0

9090000078001234 6

Sample Output

9190

100

9907000008001234

HINT

Source

/*

这道题主要是用到贪心算法，还是比较好理解

一个字符串a[n], 从a[0]开始，到a[n-1]依次与后面的进行替换

贪心规则：每次需要与后面的length-i个元素相比较，找到最大的替换到i的位置

算法：每次从头开始，以一个位置为起点，在可移动步数内找一个最大值，然后移动到起点 ，可移动步数减去当前移动步数。如果还可移动在从头开始找。

*/

import java.util.Scanner;/** * Created by fan on 17-6-30. */public class P1529 {    public static void main(String[] args) {        Scanner cin = new Scanner(System.in);        while (cin.hasNext()) {            String n = cin.next();            int k = cin.nextInt();            solve(n, k);        }        cin.close();    }    private static void solve(String s, int k) {        char a[] = s.toCharArray();       for (int i=0; i
      
       i; j--) { //找到最大元素就依次交换               char t = a[j];               a[j] = a[j-1];               a[j-1] = t;           }           k = k - (maxi - i); // 更新现在的可移动步数           //..如果还有步数则继续，从第二个元素开始继续进行贪心       }        System.out.println(new String(a));    }}