首页 > 代码库 > Codeforces Round #249 (Div. 2) B. Pasha Maximizes
Codeforces Round #249 (Div. 2) B. Pasha Maximizes
看到题目的时候，以为类似插入排序，比较第i个元素和第i-1个元素，
如果第i个元素比第i-1个元素小，则不交换
如果第i个元素比第i-1个元素大，则交换第i个元素和第i-1个元素
继续比较第i-1个元素与前一个元素，直到前一个元素大为止
交换元素次大于等于k则停止
但对测试用例
1234 3
则出现问题，如果按照上述方法得到答案为3214，
但正确答案是4321，直接将第4个元素往前交换
故在上面基础上改进得
当扫描第i个元素时，则要取出[i,i+k+1)之间的最大元素，然后将最大元素往前交换，则交换后第i个元素肯定是最大的
#include <iostream>#include <vector>#include <string>#include <algorithm>using namespace std;int main(){ string s; int k; cin >> s >> k; int len = s.length(); for(int i = 0 ; i < len; ++ i){ int maxIndex = i; for(int j = i +1; j < min(len,i+k+1); ++ j){ if(s[maxIndex] < s[j]) maxIndex = j; } for(int j = maxIndex; j > i; --j){ swap(s[j],s[j-1]); k--; } } cout<<s<<endl;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。