NYOJ-寻找最大数(3)

寻找最大数（三）

时间限制：1000 ms | 内存限制：65535 KB

难度：2

描述

给出一个整数N，每次可以移动2个相邻数位上的数字，最多移动K次，得到一个新的整数。

求这个新的整数的最大值是多少。

输入

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

输出

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

样例输入

1990 1
100 0
9090000078001234 6

样例输出

9190
100
9907000008001234

 1 #include <stdio.h>
 2 #include <string.h>
 3 int main(void){
 4     int k,i,len,max,step;
 5     char s[50];
 6     while(scanf("%s%d",&s,&k) != EOF){
 7         /**
 8             思路：以某一位置的数字为基准
 9             在i + k - step范围内寻找一个最大数前移
10         */
11         i = 0;///从0位置开始
12         len = strlen(s);
13         step = max = 0;
14         for(int j = 0; j < len && j <= k; j++)///查找前k中最大值
15             if(s[max] < s[j])
16                 max = j;
17         while(i < len){
18             if(step >= k) break;
19             if(i != max){
20                 ///将max位置移到i位置
21                 char t;
22                 while(max != i){
23                     t = s[max];
24                     s[max] = s[max-1];
25                     s[max-1] = t;
26                     max--;
27                     step++;
28                 }
29             }
30             i++;
31             ///更新max
32             max = i;
33             for(int j = i; j < len && j <= i + k - step; j++){
34                 if(s[max] < s[j])
35                     max = j;
36             }
37         }
38         printf("%s
",s);
39     }
40     return 0;
41 }