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;
}