贪心算法 nyoj1057

贪心算法

在数据结构中,我们学习过普里姆算法,是一种在无向边中查找最短路径算法. 现在来看看贪心算法,在我脑中的. 以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; }