题目
{% raw %}
你最多可以获得的馅饼数量是多少呢?
{% 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 %}
题解
没有什么好的思路,暴力搜索下
最多 10
位数,能交换 100
次
而且只能交换相邻的,数据量并不是很大
首先写好交换某相邻两位的函数,让代码更简洁同时防止思路混乱
然后依次交换相邻的两位,如果新数没有出现过,就交换后插入到 vector 中待用
(一方面是如果该数字已经查找过了,就不再查找了;另一方面是为了筛选出最大值)
然后 sort 后输出最大值即可
需要特别注意的是,虽然时间复杂度不大,但是查询和插入操作是一直在进行的,因此这里其实是主要耗费时间的地方,应该使用 lower_bound()
来 二分查找插入 ,这样能始终保证 vector 有序,节省插入和查找的时间
PS:用贪心更短,来自 Robin 的代码
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; }