首页 > 代码库 > NYOJ 1057 寻找最大数(三) (贪心)

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

题目描述

http://acm.nyist.net/JudgeOnline/problem.php?pid=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<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
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<<k<<endl;
            if(k1==len){//当前的数就是最大的数
                break;
            }
            for(i=k1;i<len&&i<=k1+k;i++){//每次从当前状态向后在k步的范围内,寻找最大值
                if(s[i]>s[k2]){
                    k2=i;
                }
            }
            //cout<<k2<<endl;
            if(k2>k1){

                for(j=k2;j>k1;j--){//找到的最大的值,向前变换k2-k1次
                    swap(s[j],s[j-1]);
                }
                k-=(k2-k1);//剩余的变换次数
            }
            k1++;//修改指针指向
            k2=k1;
        }
        printf("%s\n",s);
    }

    return 0;
}
        



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