AOJ 837.交换大法好

180


题目


点击显/隐题目



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

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






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






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








2
1990 1
1034 2






9190
3104









题解



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

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

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

然后 sort 后输出最大值即可

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




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

点击显/隐来自dalao的代码
`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;
}

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