AKOJ -- 1529 -- 寻找最大数





## 1529: 寻找最大数

Time Limit: 1 Sec  Memory Limit: 128 MB

Submit: 107  Solved: 53

上一题SubmitStatus标签打分编辑题目信息编辑测试数据下一题




## 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<a.length-1 && k!=0; i++) {
char maxc = a[i]; //maxc 存储a[i]后的最大元素
int maxi = i; //maxi 存储a[i]后的最大元素的下标
for (int j=i+1; j<=k+i && j<a.length; j++) { //for 用于查找a[i]后的最大元素(k步以内最大元素)
if (maxc < a[j]) {
maxc = a[j];
maxi = j;
}
}
for (int j=maxi; j>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));
}
}








坚持原创技术分享,您的支持将鼓励我继续创作!
  • 本文作者: Fayne
  • 本文链接: 340.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!