题目链接

microhhh的回城

解题思路

这题挺有意思的。本来寻思放在\(DS\)第一次练习赛应该不会很难吧，结果愣是卡在数据范围上写不出来。

然后暴力过掉了,但是用了\(1019ms\)。感觉可以继续优化。（放一下暴力代码，不解释了）

#include<stdio.h>
#include<string.h>
int n,m;
char map[10010][10010];//char防止卡空间
int main(){
    int i,T,j,x,c,b,l,k;
    scanf("%d",&T);
    for(k=1;k<=T;k++){
        printf("Case %d #:",k);
        memset(map,0,sizeof(map));
        scanf("%d%d%d",&n,&m,&l);
        for(i=0;i<m;i++){
            scanf("%d%d",&c,&b);
            map[c][b]=1;
            map[c+1][b]=2;
        }
        for(i=0;i<n;i++){
            x=i;
            for(j=1;j<=l;j++){
                if(map[x][j]==1)x++;
                else if(map[x][j])x--;
            }
            printf(" %d",x);
        }
        printf("\n");
    }
    return 0;
}

又在想如果在暴力模拟的时候记录一下每列的头结点，可以进行二分查找，复杂度会下来一个\(logn\)。

码量略大，不过优化了不少。代码这里就不放了。

然后突然想到其实这就是一个交换终点的问题。从下面向上每一条边都对应一次终点的交换，去掉重边即可。\(7msAC\)。

AC代码

#include<cstdio>
#include<algorithm> 
int n,m,l;
struct Path{
    int c,k;
    bool operator<(const Path&b)const{return k>b.k||(k==b.k&&c<b.c);}
}e[100010];
int pre[10010],end[10010],T,i,j,p,q,t;
int main(){
    scanf("%d",&T);
    for(j=1;j<=T;j++){
        scanf("%d%d%d",&n,&m,&l);
        for(i=0;i<m;i++)scanf("%d%d",&e[i].c,&e[i].k);
        std::sort(e,m+e);
        for(i=0;i<n;i++)pre[i]=i;
        for(i=0;i<m;i++){
            p=e[i].c,q=p+1;
            if(i&&e[i].c==e[i-1].c&&e[i].k==e[i-1].k);//去重
            else t=pre[p],pre[p]=pre[q],pre[q]=t;
        }
        printf("Case %d #:",j);
        for(i=0;i<n;i++)printf(" %d",pre[i]);
        putchar('\n');
    }
    return 0;
}