描述

佳佳刚进高中,在军训的时候,由于佳佳吃苦耐劳,很快得到了教官的赏识,成为了“小教官”。在军训结束的那天晚上,佳佳被命令组织同学们进行篝火晚会。一共有n个同学,编号从1到n。一开始,同学们按照1,2,……,n的顺序坐成一圈,而实际上每个人都有两个最希望相邻的同学。如何下命令调整同学的次序,形成新的一个圈,使之符合同学们的意愿,成为摆在佳佳面前的一大难题。

佳佳可向同学们下达命令,每一个命令的形式如下:

(b1, b2,… bm -1, bm)

这里m的值是由佳佳决定的,每次命令m的值都可以不同。这个命令的作用是移动编号是b1,b2,…… bm –1,bm的这m个同学的位置。要求b1换到b2的位置上,b2换到b3的位置上,……,要求bm换到b1的位置上。

执行每个命令都需要一些代价。我们假定如果一个命令要移动m个人的位置,那么这个命令的代价就是m。我们需要佳佳用最少的总代价实现同学们的意愿,你能帮助佳佳吗?

输入格式

输入文件fire.in的第一行是一个整数n(3 <= n <= 50000),表示一共有n个同学。其后n行每行包括两个不同的正整数,以一个空格隔开,分别表示编号是1的同学最希望相邻的两个同学的编号,编号是2的同学最希望相邻的两个同学的编号,……,编号是n的同学最希望相邻的两个同学的编号。

输出格式

输出文件fire.out包括一行,这一行只包含一个整数,为最小的总代价。如果无论怎么调整都不能符合每个同学的愿望,则输出-1。

数据规模

对于30%的数据,n <= 1000;

对于全部的数据,n <= 50000。

题解

至此我就算做完了NOIP05提高组的全部四道题,发现除了第一题外其它题都不水,对于我这样的水平来说很值得一做。过河的状态压缩我想了好久;本题优化方法较过河简单,但也需要动动脑子;至于那个等价表达式则是典型的ws题:思想简单(特值法+用栈求表达式的值),但实现起来却比较繁琐,细节硕多,稍不留神就会出错,我前后一共提交了5次才AC(得到的分数分别是20、30、40、90、100)。还好这些题都是自己独立搞出来的。顺带一提,等价表达式取特值时并不像很多人说的要多个,一个足矣,当然不要取太特殊的,比如取a=1,-2,-3,0这样的就很容易被强数据阴掉,但要是取个a=-5.65742它不就没治了;同时B4数据中括号不匹配的情况。

当然这都是题外话,下面言归正传。

首先需要看到的是,虽然佳佳下达的命令形式很ws,但是在求总代价的时候却完全不需要管它。显然,在佳佳下达完一系列诡异的命令后,最后有几个人离开了原来的位置,这种情况下最小代价就是几(为什么?)。看清了这一点,问题就转化为:要使得所有人满意,最少需要让几个人离开原来的位置?

我们先考虑无解的情况。把每个人看成无向图中的节点,两人相邻则连一条边。当n个人以某种次序围坐成一个圈的时候,每个节点的度一定都是2。而这种状态一定是初始状态通过若干次次序调整能达到的,即一定有解。那么无解的情况就一定是,根据同学们的希望构图后有同学的度不为2。这样,我们只需要构图,然后看是否所有节点的度都为2就可以判断是否有解了。

如果有解,下面就需要计算最小代价了。对于我们构得的图,DFS(1)后一定得到唯一的一个序列。例如1,5,3,2,4。我们现在就需要比较它和初始状态1,2,3,4,5,看有几个人离开了原来的位置。但这个序列实际代表的是一个环,而且方向正反有两种(即1,3,5,2,4和4,2,5,3,1应该是等价的),我们就需要把初始序列正反分别“转”N次(即1,2,3,4,5; 5,1,2,3,4; 4,5,1,2,3; 3,4,5,1,2; 2,3,4,5,1 以及 5,4,3,2,1; 1,5,4,3,2; 2,1,5,4,3; 3,2,1,5,4; 4,3,2,1,5)和DFS得到的序列比较,看其中最少有几个位置上的人编号不相同,就得到了我们要求的最小代价。

DFS是O(N)的;旋转可以通过指针来实现,所以是O(1)的;每次比较是O(N)的,共进行2N次比较。因此总的复杂度是O(N^2)的。期望得分为30分(我没写过这方法哈)。

进行很多次旋转,每次都需要比较,这种方法实在太慢了,是整个算法的瓶颈。怎么改进呢?我们发现转来转去不管怎么转,任意两个人之间的相对位置关系在这过程中都不会变。于是想到做差。

1 5 3 2 4
- 1 2 3 4 5
————-
0 3 0 3 4  (如果差小于0则加上N=5)

这表示序列1,5,3,2,4不转动时1,3两个人在原来的位置上,转动3个位置后5和2两个人在原来的位置上,转动4个位置后只有4一个人会在原来的位置上。这就是说,1,5,3,2,4与1,2,3,4,5在旋转后最多有2个位置上的人编号相同,即最少有3个位置上的人编号不相同。同理:

1 5 3 2 4
- 5 4 3 2 1
————-
1 1 0 0 3  (如果差小于0则加上N=5)

1,5,3,2,4与5,4,3,2,1在旋转后最少有3个位置上的人编号不相同。

取其中的较小者(例子没举好,两个值相同了)为3,即最后要求的最小总代价为3。问题就算解决了。

算法流程总结如下:

1. 根据输入构图,要求每个节点度只能为2,否则无解;
2. dfs得到一个序列seq表示符合条件的环
3.(下标从1开始)
    - 令a[i]=seq[i]-i(若小于0则+N)
    - a中最多有x个相等的值
    - 令b[i]=seq[i]-(N+1-i)(若小于0则+N)
    - a中最多有y个相等的值
4. n-max(x,y)即为所求

改进后的算法复杂度为O(N),实现起来很简单。期望得分为100。

代码如下:

#include <iostream>
#include <fstream>
#include <cassert>
using namespace std;
long N,seq[50001],p=1;
class{
    private:
        long nbr[50001][3];
        bool flag[50001];
        bool isnbr(long v1,long v2){
            for(int i=1;i<=nbr[v1][0];i++)
                if(nbr[v1][i]==v2)  return true;
            return false;
        }
    public:
        bool AddE(long v1,long v2){
            if(isnbr(v1,v2))    return true;
            else if(nbr[v1][0]==2||nbr[v2][0]==2)   return false;
            else{
                nbr[v1][++nbr[v1][0]]=v2;
                nbr[v2][++nbr[v2][0]]=v1;
                return true;
            }
        }
        void dfs(long i){
            assert(!flag[i]);
            flag[i]=true,seq[p++]=i;
            for(int j=1;j<=nbr[i][0];j++){
                if(!flag[nbr[i][j]]){
                    dfs(nbr[i][j]);
                    break;
                }
            }
        }
}G;
long solve(void){
    long cnt1[50001]={0},cnt2[50001]={0},ans=0;
    for(int i=1,a,b;i<=N;i++){
        a=seq[i]-i;
        if(a<0) a+=N;
        b=seq[i]-(N+1-i);
        if(b<0) b+=N;
        if(++cnt1[a]>ans)   ans=cnt1[a];
        if(++cnt2[b]>ans)   ans=cnt2[b];
    }
    return N-ans;
}
int main(){
    ifstream cin("fire.in");
    ofstream cout("fire.out");
    cin >> N;
    for(int i=1,nbr1,nbr2;i<=N;i++){
        cin >> nbr1 >> nbr2;
        if(!G.AddE(i,nbr1)||!G.AddE(i,nbr2)){
            cout << -1 << endl;
            return 0;
        }
    }
    G.dfs(1);
    cout << solve() << endl;
    return 0;
}

最后再给一个在vijos里看到的算法。我自己没有实现过,有兴趣的试试吧。

见过的最牛最简单的方法……

将此题转换为冒泡排序,记录下所有交换的次数和两数间的距离,加上就行了……—__—|||

具体是这样的,我们反向思维,本来是要求一个有序数列求出成为无序数列的代价,现在我们把无序数列(即目标数列)进行冒泡排序,然后……就是这样…… 看完之后,偶巨汗……