HDU6351 Beautiful Now(2018HDU多校联赛第五场,思路)

本文主要是介绍HDU6351 Beautiful Now(2018HDU多校联赛第五场,思路)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem Description

Anton has a positive integer n, however, it quite looks like a mess, so he wants to make it beautiful after k swaps of digits.
Let the decimal representation of n as $(x_1 x_2 \cdots x_m)_{10}$ satisfying that $1 \leq x_1 \leq 9$ , which means $n = \sum_{i = 1}^{m}{x_i 10^{m - i}}$ . In each swap, Anton can select two digits xi and xj $(1 \leq i \leq j \leq m)$ and then swap them if the integer after this swap has no leading zero.
Could you please tell him the minimum integer and the maximum integer he can obtain after k swaps?

Input

The first line contains one integer T, indicating the number of test cases.
Each of the following T lines describes a test case and contains two space-separated integers n and k.
$1 \leq T \leq 100$ , $1 \leq n, k \leq 10^9$

Output

For each test case, print in one line the minimum integer and the maximum integer which are separated by one space.

Sample Input

5
12 1
213 2
998244353 1
998244353 2
998244353 3

Sample Output

12 21
123 321
298944353 998544323
238944359 998544332
233944859 998544332

思路

给出t组数据，然后每组数据给出一个n和k，你每次可以交换任意两个数，总的交换次数不超过k次，问你在规定的次数之内这个数可以变成的最大值和最小值是多少(注意特判前导0).

因为一个数字顶多有9位，所以我们可以全排列暴力枚举排列数，复杂度就是 $9!$ ,每次枚举一个排列，计算出交换的次数如果符合条件就进行最大最小值处理。那么如何计算一个数交换几次可以变成另一个数，交换的数字必定会连成一个环，那么每个环需要交换的次数就是环内的元素个数减去1，(具体可以百度关键字使序列有序的最小交换次数)。

但是在本题中由于存在数字重复的问题，我们可以对于1到9所有的位数，提前预处理，存储一下经过多少次变换每个位置会变成什么，因为位置是不可能重复的。最后枚举一下从1~k的次数，然后转换成具体的数字求最大最小值。

代码

#include <bits/stdc++.h>
using namespace std;
#define mem(a, b) memset(a, b, sizeof(a))
const int N = 1e6 + 10;
const int inf = 999999999;
vector<int> pre[10][10]; //pre[i][j]表示i位,交换次数为j的集合
int a[10], vis[10];
void init()
{for (int k = 1; k <= 9; k++){for (int i = 1; i <= k; i++)a[i] = i;do{mem(vis, 0);int now = 0;for (int i = 1; i <= k; i++)now = now * 10 + a[i];int tmp = 0; //计算出变换需要的次数for (int i = 1; i <= k; i++)if (!vis[i]){vis[i] = 1;for (int j = a[i]; j != i; j = a[j]){vis[j] = 1;tmp++;}}pre[k][tmp].push_back(now);} while (next_permutation(a + 1, a + k + 1));}
}
int get_num(int n)
{int ans = 0;int tmp = 1;while (n){ans += a[n % 10] * tmp;n /= 10;tmp *= 10;}return ans;
}
char s[20];
void solve()
{int k;scanf("%s%d", s, &k);int n = strlen(s);if (n == 10){printf("1000000000 1000000000\n");return;}if (k >= n)k = n - 1;for (int i = 1; i <= n; i++)a[i] = s[i - 1] - '0';int maxx = 0, minn = inf;int l = 1;for (int i = 1; i < n; i++) //防止前导0l *= 10;for (int i = 0; i <= k; i++) //枚举所有的交换次数{for (auto num : pre[n][i]){int now = get_num(num); //根据位来获取值if (now < l)continue; //去除前导0maxx = max(maxx, now);minn = min(minn, now);}}printf("%d %d\n", minn, maxx);
}
int main()
{// freopen("in.txt", "r", stdin);init();int t;scanf("%d", &t);while (t--)solve();return 0;
}