题目传送门
题意:
给你 n 和 k, 你每次能交换 n 的两个位, 问最多 k 次后的最小和最大值
思路:
考虑到 n 到 1e9, 所以可以用全排列来暴力, 但是我们不能全排列之前的数位,
因为 n 中的位数可能相等, 那样很难计算交换次数, 因此我们只能全排列下标
然后我们要怎样计算每次排列的交换次数, 这里用到了循环节
比如: 0 1 2 3 4 然后 2 和 3 交换
0 1 3 2 4 那么 a[2]=3;a[3]=2; 这里就存在循环
这里就可以用来处理次数
代码:
- #include<bits/stdc++.h>
- using namespace std;
- #define INF 0x3f3f3f3f
- int T;
- int n,k;
- char s[25];
- int a[25];
- int vis[25];
- int len;
- bool check()// 检查次数
- {
- for(int i=0;i<len;i++) vis[i]=0;
- int ans=0;
- for(int i=0;i<len;i++)
- {
- if(vis[i]) continue;
- int cnt=0;
- while(vis[i]==0)
- {
- cnt++;
- vis[i]=1;
- i=a[i];
- }
- ans+=cnt-1;
- if(ans>k) return false;
- }
- return true;
- }
- int main()
- {
- scanf("%d",&T);
- while(T--)
- {
- scanf("%s %d",&s,&k);
- len=strlen(s);
- for(int i=0;i<len;i++)
- a[i]=i;
- int minn=INF,maxn=0;
- do{
- if(s[a[0]]!='0'&&check())// 首位不为 0
- {
- int ans=0;
- for(int i=0;i<len;i++)
- {
- ans=ans*10+s[a[i]]-'0';
- }
- minn=min(minn,ans);
- maxn=max(maxn,ans);
- }
- }while(next_permutation(a,a+len));
- printf("%d %d\n",minn,maxn);
- }
- return 0;
- }
- View Code
参考博客: https://blog.csdn.net/smilelingling/article/details/81542938
来源: http://www.bubuko.com/infodetail-2961992.html