Codeforces Round #598 (Div. 3)-B. Minimize the Permutation(1400思维+贪心+排序)

本文主要是介绍Codeforces Round #598 (Div. 3)-B. Minimize the Permutation(1400思维+贪心+排序)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

B. Minimize the Permutation

飞机票

题意：
给你从1-n的全排列，每个位置有且只能进行一次置换，置换是当前位置和下一位置交换，求能得到的字典序最小的全排列是什么，输出它
思路：
贪心的去思考，既然要全排列最小，那么肯定是在能交换的情况下对数列中最小的数进行交换放在当前位置，又因为数据范围很小，于是我用flag标机当前位置，用map记录每个数的位置，暴力的去扫1-n中哪些数可以置换，置换条件就是当前数的位置比flag大，贪心的去完成就行

#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
int a[maxn];
int main()
{int n,i,j,t,q;cin>>t;while(t--){cin>>n;map<int,int>mo;for(i=1;i<=n;i++){cin>>a[i];mo[a[i]]=i;}int flag=1;for(i=1;i<=n;i++){if(mo[i]>flag){for(j=mo[i];j>=flag+1;j--){a[j]=a[j-1];mo[a[j]]=j;}a[flag]=i;int d2=mo[i];mo[i]=flag;flag=d2;}else if(mo[i]==flag){flag++;}}for(i=1;i<=n;i++) cout<<a[i]<<" ";cn;}return 0;
}

这篇关于Codeforces Round #598 (Div. 3)-B. Minimize the Permutation(1400思维+贪心+排序)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---