Articles12
Tags2
Categories0

CF1256B-Minimize the Permutation题解

这道题。。比赛时候甚至写炸了 555 我太菜了

题解:因为每个交换只能用一次 而且数据范围贼小 直接n2暴力即可

方法:从1枚举到N 当枚举到一个i时 贪心地把i往前移动,如果当前所在位置的移动机会已经用掉或者前面一个数比当前的数要小 则停止移动

n2是因为我懒得写VIS数组了。。直接暴力找 on的解法也很容易写

上代码

n2

#include<bits/stdc++.h>
using namespace std;
const int maxn=110+50;
typedef long long ll;
int a[maxn];
int vis[maxn];
int main(){
    int t,n;
    scanf("%d",&t);
    while(t--){
        memset(vis,0,sizeof(vis));
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        for(int i=1;i<=n;i++){
            int now;
            for(int j=1;j<=n;j++){
                if(a[j]==i){
                    now=j;break;
                }
            }
            for(int j=now;j>=2;j--){
                if(!vis[j-1]&&a[j]<a[j-1]){
                    swap(a[j],a[j-1]);
                    vis[j-1]=1;
                }else{
                    break;
                }
            }
        }
        for(int i=1;i<=n;i++)
        printf("%d ",a[i]);
        printf("\n");
    }
}

on 加了个pos数组存储位置 实时更新

#include<bits/stdc++.h>
using namespace std;
const int maxn=110+50;
typedef long long ll;
int a[maxn];
int vis[maxn];
int pos[maxn];
int main(){
    int t,n;
    scanf("%d",&t);
    while(t--){
        memset(vis,0,sizeof(vis));
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            pos[a[i]]=i;
        }
        for(int i=1;i<=n;i++){
            int now=pos[i];
            for(int j=now;j>=2;j--){
                if(!vis[j-1]&&a[j]<a[j-1]){
                    swap(pos[a[j]],pos[a[j-1]]);
                    swap(a[j],a[j-1]);
                    vis[j-1]=1;
                }else{
                    break;
                }
            }
        }
        for(int i=1;i<=n;i++)
        printf("%d ",a[i]);
        printf("\n");
    }
}

。。多练吧QAQ

Author:西瓜喵喵.
Link:https//:ForgGYLH.github.io/2019/11/05/CF1256b-Minimize%20the%20Permutation%E9%A2%98%E8%A7%A3/
版权声明:本文采用 CC BY-NC-SA 3.0 CN 协议进行许可