贪心算法 nyoj1057

2019-11-14 09:55:39

字体：大中小

来源：转载

供稿：网友

贪心算法

在数据结构中,我们学习过普里姆算法,是一种在无向边中查找最短路径算法. 现在来看看贪心算法,在我脑中的. 以NYOJ1057为例描述给出一个整数N，每次可以移动2个相邻数位上的数字，最多移动K次，得到一个新的整数。

求这个新的整数的最大值是多少。输入多组测试数据。每组测试数据占一行，每行有两个数N和K (1?≤?N≤?10^18; 0?≤?K?≤?100).输出每组测试数据的输出占一行，输出移动后得到的新的整数的最大值。样例输入 1990 1 100 0 9090000078001234 6 样例输出 9190 100 9907000008001234 来源原创上传者 TC_李远航 1. 首先从数字的第一位开始遍历2. 每一次遍历的最后一个点,是可以用的步数 3. 直到步数等于0 就输出 4. 每一次在可用步数中查找最大个数 5. 记录下标,然后用步数减去下标加上起点 6. 在找到最大值后对数据进行交换位置的处理

#include <iostream>#include <cstdio>using namespace std;#include <string.h>char num[19];int main(){ int k ; while(cin>>num>>k){ if(k==0){ cout << num << endl; continue; } //sPRintf(num, "%d", n); int length = strlen(num); int start = 0 ; //从第一个开始遍历 int step = 0; //交换次数不可以超过k多少步; char tmp ; for( int i = 0 ; i < length ; i++ ){ tmp = num[i];//初始比较值 int index = 0; int flag = 1; for(int j = i+1 ; j<=i+k && j<length ; j++){//从i 后面一个开始查找最大数查找范围是现有步长之内 if(num[j]>tmp){ tmp = num[j]; index = j; flag = 0 ; } } if(!flag){ for( int q=index; q>i ; q--){ tmp = num[q]; num[q] = num[q-1]; num[q-1] = tmp; } k = k - index + i; } if(k==0){ break; } } cout << num<< endl; } return 0;}

上一篇：帮助别人也是帮助自己，字符串

下一篇：bzoj 3924: [Zjoi2015]幻想乡战略游戏（树链剖分）

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注