CF-Div.3-B. Minimize the Permutation【模拟·需要清醒的脑子】

题目传送门

根据字典序，是个人都会想到依次把目前最小的数尽量往前面移动，直到它不能再往前移动，或者已经到了它的期望位置（就是排列的那个位置 比如$i$就应该在位置$i$）为止。

所以我刚开始是这么写的：

 #include<cstdio>
 #include<algorithm>
 #include<cstring>
 #include<vector>
 using namespace std;
 #define N 105
 #define ll long long
 int n;
 int a[N],pos[N];
 bool vis[N];
 int main()
 {
     int T;scanf("%d",&T);
     while(T--)
     {
         scanf("%d",&n);
         for(int i=;i<=n;i++)
         {
             scanf("%d",&a[i]);
             vis[i]=,pos[a[i]]=i;
         }
         int t=;
         while()
         {//第i次 i和i+1交换
             //printf("**%d %d\n",t,pos[t]);
             if(t>=n) break;
             if(vis[pos[t]-])
             {//这一个数不能再往前挪了
                 t++;
                 continue;
             }
             if(pos[t]<=t)
             {
                 t++;
                 continue;
             }
             vis[pos[t]-]=;
             int tmp=a[pos[t]-];
             a[pos[t]-]=a[pos[t]],a[pos[t]]=tmp;
             pos[tmp]++,pos[t]--;
             //for(int i=1;i<n;i++)
             //    printf("%d ",a[i]);
             //printf("%d \n",a[n]);
         }
         for(int i=;i<n;i++)
             printf("%d ",a[i]);
         printf("%d \n",a[n]);
     }
     return ;
 }
 /*
 1
 4
 4 2 1 3
 */
 /*
 //-----
             if(t>a[pos[t]-1])
             {
                 t++;
                 continue;
             }
             //-----
 */

Code

然后$WA$了，一直调调调…自闭ing

后来打了一个对拍，可惜拍出来数据很大，就把错了的地方调出来，然后离散化长这个样子：

1
4
4 2 1 3

啊，我错了，应该是要现在这个数小于前面那个数才能交换，而不是搞什么期望位置啊，因为前面有可能有一些比较小的数不能够到达他的期望位置，然后就被无辜得换到后面去了。

 #include<cstdio>
 #include<algorithm>
 #include<cstring>
 #include<vector>
 using namespace std;
 #define N 105
 #define ll long long
 int n;
 int a[N],pos[N];
 bool vis[N];
 int main()
 {
     int T;scanf("%d",&T);
     while(T--)
     {
         scanf("%d",&n);
         for(int i=;i<=n;i++)
         {
             scanf("%d",&a[i]);
             vis[i]=,pos[a[i]]=i;
         }
         int t=;
         while()
         {//第i次 i和i+1交换
             //printf("**%d %d\n",t,pos[t]);
             if(t>=n) break;
             if(vis[pos[t]-])
             {//这一个数不能再往前挪了
                 t++;
                 continue;
             }
             //-----
             if(t>a[pos[t]-])
             {
                 t++;
                 continue;
             }
             //-----
             vis[pos[t]-]=;
             int tmp=a[pos[t]-];
             a[pos[t]-]=a[pos[t]],a[pos[t]]=tmp;
             pos[tmp]++,pos[t]--;
             //for(int i=1;i<n;i++)
             //    printf("%d ",a[i]);
             //printf("%d \n",a[n]);
         }
         for(int i=;i<n;i++)
             printf("%d ",a[i]);
         printf("%d \n",a[n]);
     }
     return ;
 }
 /*
 1
 4
 4 2 1 3
 */

Code

这是我做过的最自闭的一场Div.3