289

2
1990 1
1034 2

9190
3104

# 题解

(一方面是如果该数字已经查找过了,就不再查找了;另一方面是为了筛选出最大值)

PS：用贪心更短,来自 Robin 的代码

cpp 来自dalao的代码
#include
using namespace std;
char s[15];
int a[15], b[15], f[15];

void swap(int a, int b) {
int temp = *a;
a = b;
*b = temp;
}

int main() {
int T, k;
cin >> T;
while (T--) {
cin >> s >> k;
int len = strlen(s);
if (len == 1) {
cout << s << endl;
continue;
}
for (int i = 0; i < len; ++i) {
a[i] = s[i] - '0';
b[i] = a[i];
}
int maxnum = -1, maxid;
for (int i = 0; i < len; ++i) {
if (k <= 0) break;
maxnum = b[i]; maxid = i;
for (int j = i; j <= i + k && j < len; ++j) {
if (b[j] > maxnum) {
maxnum = b[j];
maxid = j;
}
}
k -= maxid - i;
for (int x = maxid; x > i; --x)
swap(&b[x], &b[x-1]);
}
for (int i = 0; i < len; ++i)
cout << b[i];
cout << endl;
}

return 0;
}
</div>

<br><br>

# 代码
<div><div class="fold_hider"><div class="close hider_title">点击显/隐代码</div></div><div class="fold">cpp 交换大法好 https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
/*/
#define debug
#include <ctime>
//*/
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long LL;

const int maxn = 12;

struct Node{
LL n;
int k;
Node(LL a,int b):n(a),k(b){}
};

LL POW(LL a,int n) {
LL t;
if(n == 0) return 1;
if(n == 1) return a;
t = POW(a,n / 2);
t = t * t;
if((n & 1) == 1)t = t * a;
return t;
}

LL swap(LL n,int a,int b){
LL t1 = (n/POW(10,a-1)) % 10LL;
LL t2 = (n/POW(10,b-1)) % 10LL;

n = n - t1 * POW(10,a-1) - t2 * POW(10,b-1) + t1 * POW(10,b-1) + t2 * POW(10,a-1);
return n;
}

queue<Node> Q;
vector<LL> v;

LL bfs(LL n,int k){
while(!Q.empty())Q.pop();
v.clear();

int size = 0;
LL temp = n;
while(temp){
temp/=10;
size++;
}

Q.push(Node(n,0));
v.push_back(n);
while(!Q.empty()){
LL tn = Q.front().n;
int tk = Q.front().k;
Q.pop();

if(tk < k){
for(int i=1;i<size;i++){
LL tt = swap(tn,i,i+1);

if(lower_bound(v.begin(),v.end(),tt) == v.end()){
v.insert(lower_bound(v.begin(),v.end(),tt),tt);
Q.push(Node(tt,tk+1));
}
}
}
}
sort(v.begin(),v.end());
for(size_t i=0;i<v.size();i++)
cout<<v[i]<<" ";
cout<<endl;
return v[v.size()-1];
}

int main(){
#ifdef debug
freopen("in.txt", "r", stdin);
int START = clock();
#endif
cin.tie(0);
cin.sync_with_stdio(false);

int T;
cin >> T;
while(T--){
LL n;
int k;
cin >> n >> k;
cout << bfs(n,k) << endl;
}

#ifdef debug
printf("Time:%.3fs.\n", double(clock() - START) / CLOCKS_PER_SEC);
#endif
return 0;
}


• 点击查看/关闭被识别为广告的评论