CodeForces - 1256B Minimize the Permutation（思维模拟）

题目链接：https://vjudge.net/contest/341054#problem/B


解析：
长度为n的一个排列（这个排列为n个数，从1到n）
最多进行n-1次操作
对于第i次操作，可以交换i和i+1位置上的数字
每一个位置交换后，就不能再进行交换了。
保证进行若干次操作后，能有最小的排列。输出这个最小的排列。
分析：
首先明白长度相同的两个序列，Note中的解释很好的说明了如何判定排列p和q的大小。
思想就是贪心：先把最小的数字移到第一位，再移动次小的数字，以此类推。。。
举例：序列 5 4 1 3 2
先把数字1移动到第一位，得到序列1 5 4 3 2，此时i=2和i=1的位置已经移动过
再考虑把数字2往前移，得到序列1 5 2 4 3，此时i=4和i=3的位置也被移动过
把数字1和2移动过后，所有的位置都被移动过了，已经不能再进行移动
所以最小的序列就是1 5 2 4 3
此题时间有限制，必须得考虑到位，刚开始我是考虑

  for(int i=1; i<=n; i++)
        {
            for(int j=v; j<=n; j++)
            {
                if(a[j]==i)/*找到i的位置,但不是和本身一一对应*/
                {
                    int k=j;
                    while(num>0&&k>v)
                    {
                        if(book[k-1])
                            continue;
                        if(a[k-1]<a[k])
                            break;
                        swap(a[k-1],a[k]);
                        book[k-1]=1;
                        num--;
                        if(num==0)
                        {
                            flag=1;
                            break;
                        }
                        k--;
                    }
                    v++;
                    break;
                }
            }
            if(flag)
                break;
        }

对于两层for循环，从小到大遍历每一个元素，并找到此元素在其序列中的位置，然后对于没有交换过的位置进行交换，并对num的值进行–。其实对于num的判断是可以直接放在外边的。
正确代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e2+10;
int n,a[N],book[N];
int main()
{
    int q;
    scanf("%d",&q);
    while(q--)
    {
        memset(book,0,sizeof(book));
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
            scanf("%d",&a[i]);
        int num=n-1,k=1;
        while(k<=n&&num>0)
        {
            for(int i=1; i<=n; i++)
            {
                if(a[i]==k)/*找到元素k在其序列中的位置*/
                {
                    for(int j=i-1; j>=k; j--)
                    {
                        if(book[j])
                            continue;
                        if(a[j]<a[j+1])
                            break;
                        //对于这个for循环,结束条件就是a[j]<a[j+1],
                        //这个地方与num的值是无关的,因为每个位置最多就会被移动一次,移动过的位置会被直接跳过去
                        swap(a[j],a[j+1]);
                        book[j]=1;
                        num--;
                    }
                    k++;/*不管是否是按顺序移动位1 2 。。。n,k都要++*/
                    break;
                }
            }
        }
        for(int i=1; i<=n; i++)
            printf("%d ",a[i]);
        printf("\n");
    }
    return 0;
}