「题解」生日礼物

题目链接:GMOJ 1310

题目

题目描述

Alice 收到一份来自美国的生日礼物:一个崭新的双链火车(如下图),火车有 $N$ 节车厢,依次编号为 $1$ 到 $N$,你可以在该玩具上进行两种操作:

  • A:把 $X$ 号车厢移到 $Y$ 号车厢前面;
  • B:把 $X$ 号车厢移到 $Y$ 号车厢后面。

Alice 收到礼物后很兴奋,玩了数小时,记录下每一步的操作以至于他能还原到最初的状态(从左到右,按照 $1$ 到 $N$ 的顺序排列)。

当他要进行还原的时候,Alice 发现无法进行反操作恢复原貌,只能请你帮忙写一个程序计算出最少需要多少次操作才能回到原始状态。

题解

思路

考虑什么情况下(如何操作)才可以使得步数最少。
显然,位置的移动是相对的,根据这一点,我们发现,在移动的过程中可能存在某些点的相对位置没有发生过改变。
注:如果这样的点不存在,那么我们随便认定一个点的位置不变即可继续思考。

猜想:当我们选定最长单调上升子序列上的点位置不变时,移动次数最少。

证明

假设我们选择了一个最长单调上升子序列和一个点(不在最长单调上升子序列上)。
那么这一个点的位置必定在子序列的头尾之间,并且值也在最小值与最大值之间。
显然,对于这样的点,我们要花费一次移动次数才能将它放回到原始状态。
这与我们选定它不变的假设矛盾,假设不成立。
证毕。
所以我们需要求出序列的最长单调上升子序列长度 $l$,然后答案就是 $n-l$。

此外,求出序列需要使用双向链表:
– 修改操作:$\Theta(1)$;
– 查询操作:$\Theta(n)$。

求出序列后可以放到数组里面,查询操作的复杂度降为 $\Theta(1)$。

代码

代码没什么好说的,注意细节。

#include<cstdio>
#include<cstring>
#include<algorithm>
using std::min;
using std::max;
using std::lower_bound;
#include<iostream>
using std::cin;
#define INF 0X7F7F7F7F
//以上是头文件
const int MAXN=500000+5;//最大数据范围
char ch;
int n,m;
int l[MAXN],r[MAXN];
int cnt,a[MAXN],f[MAXN];
void A(int,int);//对应操作A
void B(int,int);//对应操作B
int main(void){
    register int i;
    scanf("%d%d",&n,&m);
    l[0]=n,r[n]=0;//双向链表初始化
    for(i=0;i<=n;++i){//双向链表初始化
        l[i]=i-1;
        r[i]=i+1;
    }
    for(i=1;i<=m;++i){//输入并执行操作
        static int x,y;
        cin>>ch;
        scanf("%d%d",&x,&y);
        if(ch=='A')
            A(x,y);
        if(ch=='B')
            B(x,y);
    }
    for(i=r[0];i;i=r[i])//把序列放到数组里面,降低查询的复杂度
        a[++cnt]=i;
    memset(f,0X7F,sizeof(f));
    for(i=1;i<=n;++i)//nlogn求LIS
        *lower_bound(f,f+n,a[i])=a[i];
    printf("%lld\n",n-(lower_bound(f,f+n,INF)-f));//输出答案
    return 0;
}
void A(int x,int y){
    r[l[x]]=r[x];
    l[r[x]]=l[x];
    //先把x提出来
    l[x]=l[y];
    r[l[y]]=x;
    //再把x与y前面的连起来
    r[x]=y;
    l[y]=x;
    //最后把x与y连接
    return;
}
void B(int x,int y){
    r[l[x]]=r[x];
    l[r[x]]=l[x];
    //先把x提出来
    r[x]=r[y];
    l[r[y]]=x;
    //再把x与y后面的连起来
    l[x]=y;
    r[y]=x;
    //最后把x与y连接
    return;
}