【题目链接】

题目意思

给你T组数据，每组数据给你两个正整数n,k，你每次可以交换任意两个数，总的交换次数不超过k次，问你在k次之内这个数可以变成的最大值和最小值是多少

思路分析

下面所有思路分析都是看了杜老师代码才想到的。

首先对其预处理，枚举所有可能情况（init函数）：
枚举1-9的全排列，假设当前枚举到6，判断当前的排列是由123456经过多少次数字交换得到的，然后我们计算出这个排列的数值并压入v[6][交换次数]。

代码中v[i][j]指的是里面存的是i位数字，并且可以通过j次交换，将里面的数字转化为123…i。

apply函数用来计算若数字下标按*it所指示的下标位置构成的新数字。此处apply函数传入一个数字（用来指示下标的数字），返回原数字按照 传入数字所指示下标顺序重排所构成的数字。

我们来看一组案例213 1，以它的下标作为索引，计算其下标交换0次，1次所能构成的新数字，所以我们要遍历v[3][0],v[3][1]，（定义原数字213，第一位下标为1，第二位下标为2，第三位为三）然后根据他们里面存的数字来将213重排，每一次重排，为了防止出现前导0，需要加一个判断，然后比较每一次所出现的值的大小，输出最大最小值。

由于这里涉及到重排比较麻烦，所以考虑使用数组存整数n，然后每次需要用到值的实话，再求出来。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
vector<int>v[10][10];
char s[100];
int k, flag;
int book[15], a[15];
void init()
{
    for (int n = 1; n <= 9; n++)
    {
        for (int i = 1; i <= n; i++)
            a[i] = i;
        memset(book, 0, sizeof(book));
        do
        {
            int now = 0;
            for (int i = 1; i <= n; i++)
            {
                now *= 10;
                now += a[i];
            }
            flag++;
            int temp = 0;
            for (int i = 1; i <= n; i++)
            {
                if (book[i] != flag)
                {
                    book[i] = flag;
                    for (int j = a[i]; i != j; j = a[j])
                    {
                        book[j] = flag;
                        temp++;
                    }
                }
            }
            v[n][temp].push_back(now);
        } while (next_permutation(a + 1, a + n + 1));
    }
}
int apply(int k)
{
    int mul = 1;
    int ans = 0;
    while (k)
    {
        ans += a[k % 10] * mul;
        k /= 10;
        mul *= 10;
    }
    return ans;
}
int main()
{
    init();
    int t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%s %d", s, &k);
        if (strlen(s) == 10)
        {
            printf("1000000000 1000000000\n");
            continue;
        }
        int mx = 0;
        int mn = 10000000000;
        if (k >= strlen(s))
            k = strlen(s) - 1;
        for (int i = 1; i <= strlen(s); i++)
            a[i] = s[i - 1] - '0';
        int ff = 1;
        for (int i = 1; i < strlen(s); i++)
            ff *= 10;
        for (int i = 0; i <= k; i++)
        {
            for (auto it = v[strlen(s)][i].begin(); it != v[strlen(s)][i].end(); it++)
            {
                int temp = apply(*it);
                if (temp < ff)
                    continue;
                mx = max(mx, temp);
                mn = min(mn, temp);
            }
        }
        printf("%d %d\n", mn, mx);
    }
}