題意：給定一個(gè)1-n的排列，用不超過2*n2的操作把他變成升序。每次操作只有兩種，一種是交換前兩個(gè)元素，另外一種是把最后一個(gè)元素放到最后一位。

思路：貪心。用雙端隊(duì)列來保存數(shù)據(jù)，每次當(dāng)v[0]>v[1]&&v[0]!=n時(shí)用交換前兩個(gè)的策略把當(dāng)前排好，否則就放后面等待被排。

code：

#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <cstring> #include <sstream> #include <string> #include <vector> #include <list> #include <queue> #include <stack> #include <map> #include <set> #include <bitset>using namespace std;typedef long long ll; typedef unsigned long long ull; typedef long double ld;const int INF=0x3fffffff; const int inf=-INF; const int N=180005; const int M=2005; const int mod=1000000007; const double pi=acos(-1.0);#define cls(x,c) memset(x,c,sizeof(x)) #define cpy(x,a) memcpy(x,a,sizeof(a)) #define fr(i,s,n) for (int i=s;i<=n;i++) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define lrt rt<<1 #define rrt rt<<1|1 #define middle int m=(r+l)>>1 #define lowbit(x) (x&-x) #define pii pair<int,int> #define mk make_pair #define IN freopen("in.txt","r",stdin); #define OUT freopen("out.txt","w",stdout);deque<int>v; int s[N],len;int check() {fr (i,1,v.size()-1)if (v[i]<v[i-1]) return 0;return 1; } int main() {int T,n,x;//scanf("%d",&T);while (~scanf("%d",&n)&&n){v.clear();len=0;fr (i,1,n) scanf("%d",&x),v.push_back(x);while (!check()){if (v[0]>v[1]&&v[0]!=n){swap(v[0],v[1]);s[len++]=1;//s='1'+s;//cout<<"bug1"<<endl;}else{int t=v.back();v.pop_back();//cout<<t<<endl;v.push_front(t);s[len++]=2;//s='2'+s;}}for (int i=len-1;i>=0;i--) printf("%d",s[i]);puts("");//cout<<s<<endl;} }

總結(jié)

以上是生活随笔為你收集整理的uva 11925——Generating Permutations的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。