首页 > 代码库 > 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 寻找最大数(三) (贪心)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。