AOJ 837.交换大法好|OhYee 博客

这是一篇最后编辑于 8 年前的文章，其内容可能与目前实际情况差异较大，请注意甄别

题目

{% raw %}

{% endraw %} 有一天，天上掉馅饼了。不过不是直接掉馅饼，是告诉你你将要得到的馅饼的数量a。聪明的你得到了一种魔法，可以在整数a中交换任意两个相邻的数字。而这种魔法，你最多只能使用k次。你使用魔法操作a，得到的最大的结果就是你最终获得的馅饼数量。

你最多可以获得的馅饼数量是多少呢？

{% raw %}

{% endraw %}

第一行，一个数字n(1<=n<=60)。代表测试数据数量。
接下来n行，每行两个整数a和k（1<=a<=1,000,000,000; 0<=k<=100)。

{% raw %}

{% endraw %}

输出n行，每行一个整数，代表你最多使用魔法k次，可以得到的最大的数字。

{% raw %}

{% endraw %}

2
1990 1
1034 2

{% raw %}

{% endraw %}

9190
3104

{% raw %}

{% endraw %}

题解

没有什么好的思路,暴力搜索下
最多 10 位数,能交换 100 次
而且只能交换相邻的,数据量并不是很大

首先写好交换某相邻两位的函数,让代码更简洁同时防止思路混乱

然后依次交换相邻的两位,如果新数没有出现过,就交换后插入到 vector 中待用
(一方面是如果该数字已经查找过了,就不再查找了;另一方面是为了筛选出最大值)

然后 sort 后输出最大值即可

需要特别注意的是,虽然时间复杂度不大,但是查询和插入操作是一直在进行的,因此这里其实是主要耗费时间的地方,应该使用 lower_bound() 来 二分查找插入 ,这样能始终保证 vector 有序,节省插入和查找的时间

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;
}

推荐订阅源

OhYee 博客

题目

题解