NYOJ 1057 寻找最大数（三） (贪心)

题目描述

?

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

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

输入多组测试数据。
每组测试数据占一行，每行有两个数N和K (1?≤?N≤?10^18; 0?≤?K?≤?100).输出每组测试数据的输出占一行，输出移动后得到的新的整数的最大值。样例输入

1990 1
100 0
9090000078001234 6

样例输出

9190
100
9907000008001234

题目分析：

贪心算法，但是对每一步进行贪心，应该是在k步的范围内找到最大的值，往前依次交换，如果找到了最大的值，但是没有到k步，那么对接下来的kk步继续从当前最优往后寻找。

?

AC代码：

?

 
#include
    
     
#include
     
       #include
      
        #include
       
         using namespace std; int main() { long long n; int k; while(scanf(%lld%d,&n,&k)!=EOF){ char s[20]; sprintf(s,%lld,n); int len=strlen(s); int k1,k2,i,j; k1=k2=0; while(k){ //cout<
        
         s[k2]){ k2=i; } } //cout<
         
          k1){ for(j=k2;j>k1;j--){//找到的最大的值，向前变换k2-k1次 swap(s[j],s[j-1]); } k-=(k2-k1);//剩余的变换次数 } k1++;//修改指针指向 k2=k1; } printf(%s ,s); } return 0; } 
         
        
       
      
     
    

?