撰写http://www.bubuko.com/infodetail-2716790.html
题意：给一个数字串，以及k，任意交换k次两个数的位次，输出最小最大串
题解：一开始想着直接模拟，后来发现模拟必须按照一定的顺序，也就是相同的最小数的位次上应该换的数要按照从右到左的顺序进行排序，比如k=1时，293171换成193172,k = 2时要换成193279 也就是1的位置上的数应该按照（在满足k次的情况下）从大到小的顺序从右向左排，大概开个数组存储能过，但是懒得…而且怕超时。后来想着后面的情况直接dfs，但是因为基本功太差并且看到无数人TLE以及无数人0ms过，就想着难道是找规律？？？放弃了dfs。结果dfs就是0ms…
1 将该串分别排序出两个标准非递减非递增串，然后非递减串第一个不能为0.
2 对于非递减串，在第一次找最小时的条件是!=0,其他没什么
3 在匹配上时，另x++,未匹配上则手动匹配（dfs遍历所有，记得解除标记），x++,cnt++
4 直到cnt=k或者匹配了整个串，GG
需要注意的是，按照选择排序来说，一个串最多排n-1次就有序了，所以k>=n-1时直接输出标准串即可，另外，一个串交换成有序需要n-置换环数，比如 {5 1 3 2 4 7 6 8 } ,求将这个序列变成升序序列的最小交换次数，那么这个序列中的环有 { 5 ,1,2,4},{7,6},{3},{8},那么最小交换次数就是 8-4，求降序的最小交换次数，只需要将序列逆置，再进行求解 。
代码:
#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#define ls (r<<1)
#define rs (r<<1|1)
#define debug(a) cout << #a << " " << a << endl
using namespace std;
typedef long long ll;
const ll maxn = 1e2+10;
const ll mod = 998244353;
const double pi = acos(-1.0);
ll n, m;
bool cmp( char p, char q ) {
return p > q;
}
string strmin, strmax, s, tmin, tmax;
void dfs1( ll x, ll cnt, string t ) {
if( cnt > n-1 || x == t.length()-1 ) {//超出边界或者超出次数
strmin = min(strmin,t);//选择小的
return ;
}
if( t[x] == tmin[x] ) {//如果与目标相同，则下一个，而cnt不加
dfs1(x+1,cnt,t);
return ;
}
char c = 'a';
//一定会找到最小值，若全为0，在上一步就已经匹配完成
for( ll i = x+1; i < t.length(); i ++ ) {//找到最小值（第一次时不为0）
if( t[i] <= c ) {
if( x == 0 && t[i] == '0' ) {
continue;
}
c = t[i];
}
}
for( ll i = x+1; i < t.length(); i ++ ) {//到这里的话说明与目标不一样，找到所有目标，并遍历所有情况
if( t[i] == c ) {
swap(t[i],t[x]);
dfs1(x+1,cnt+1,t);
swap(t[i],t[x]);
}
}
}
void dfs2( ll x, ll cnt, string t ) {
if( cnt > n-1 || x == t.length()-1 ) {
strmax = max(strmax,t);
return ;
}
if( t[x] == tmax[x] ) {
dfs2(x+1,cnt,t);
return ;
}
char c = '0';
for( ll i = x+1; i < t.length(); i ++ ) {
if( t[i] >= c ) {
c = t[i];
}
}
for( ll i = x+1; i < t.length(); i ++ ) {
if( t[i] == c ) {
swap(t[i],t[x]);
dfs2(x+1,cnt+1,t);
swap(t[i],t[x]);
}
}
}
string rev( string s ) {//一开始获得的序列是反的
string t = "";
for( ll i = 0, j = s.length()-1; i < s.length(); i ++, j -- ) {
t = t + s[j];
}
return t;
}
int main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);//打消iostream的输入 输出缓存
ll T, t = 1;
cin >> T;
while( T -- ) {
s = "";
ll j = 0;
cin >> m >> n;
while(m) {
char c = (m%10)+'0';
s = s + c;
m /= 10;
}
s = rev(s);
tmin = s, tmax = s;
sort(tmin.begin(),tmin.end());
sort(tmax.begin(),tmax.end(),cmp);
if( tmin[0] == '0' ) {//如果第一个是0，则找下一个不是的替换
char c = 'a';
ll inx = -1;
for( ll i = 1; i < tmin.length(); i ++ ) {
if( tmin[i] != '0' && tmin[i] < c ) {
c = tmin[i];
inx = i;
}
}
if( inx != -1 ) {
swap(tmin[inx],tmin[0]);
}
}
if( n >= s.length()-1 ) {
cout << tmin << " " << tmax << endl;
} else {
strmin = s;
dfs1(0,0,strmin);
strmax = s;
dfs2(0,0,strmax);
cout << strmin << " " << strmax << endl;
}
}
return 0;
}