OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【CTSC2007】风铃

【题目描述】

你准备给弟弟Ike买一件礼物,但是,Ike挑选礼物的方式很特别:他只喜欢那些能按照他的特有方式排成有序的东西。

你准备给Ike买一个风铃。风铃是一种多层的装饰品,一般挂在天花板上。每个风铃都包含一些由竖直的线连起来的水平杆。每根杆的两端都有线连接,下面或者挂着另一根水平杆,或者挂着一个玩具。下面是一个风铃的例子:



为使你的弟弟满意,你需要选一个满足下面两个条件的风铃:

(1)所有的玩具都在同一层(也就是说,每个玩具到天花板之间的杆的个数是一样的)或至多相差一层。

(2)对于两个相差一层的玩具,左边的玩具比右边的玩具要更靠下一点。

风铃可以按照下面的规则重新排列:任选一根杆,将杆两端的线“交换”。也就是解开一根杆左右两端的线,然后将它们分别绑到杆的另一端。注意这个操作不会改变下面的杆上线的排列顺序。

由于你正在参加信息学奥林匹克的训练,所以你决定设计一个算法,判断能否通过重新排列,将一个给定的风铃变为Ike喜欢的样子。

考虑上面的例子,上图中的风铃满足条件(1),却不满足条件(2)——最左边的那个玩具比它右边的要高。

但是,我们可以通过下面的步骤把这个风铃变成一个Ike喜欢的形式:

1.第一步,将杆1的左右两端交换,这使得杆2和杆3的位置互换,交换的结果如下图所示:



2.第二步,也是最后一步,将杆2的左右两端交换,这使得杆4到了左边,原来在左边的玩具到了右边,交换的结果如下图所示:



现在这个风铃就满足Ike的条件了。

你的任务是:给定一个风铃的描述,求出最少需要多少次交换才能使这个风铃满足Ike的条件(如果可能的话)。

【输入】

输入的第一行包含一个整数n,表示风铃中有多少根杆。

接下来的n行描述杆的连接信息。这部分的第i行包含两个由空格分隔的整数li和ri,描述杆i的左右两端悬挂的东西。如果挂的是一个玩具,则对应的值为-1,否则为挂在下面的杆的编号。

如果杆i下面挂有其它杆,则这些杆的编号将严格大于i。杆1位于风铃的顶部。

【输出】

输出仅包含一个整数。表示最少需要多少次交换能使风铃满足Ike的条件。如果不可能满足,输出-1。

【输入样例】

6

2 3

-1 4

5 6

-1 -1

-1 -1

-1 -1

【输出样例】

2

【数据范围】

1≤n≤100000

【题解】

看起来比较神的题,但由于树的性质,可以从局部开始分析这道题。将“风铃”树dfs,维护每个节点所有儿子中的最大深度和最小深度。

对于每个节点,只有四种情况:

①左右儿子都是风铃,这时候最大深度和最小深度都是1,且不用交换;

②只有左儿子是风铃,这时候最小深度是1,最大深度是右儿子的最大深度+1。注意到交换操作不改变当前节点的最大最小深度,如果最小深度和最大深度相差超过1,那就一定无解。判断有解后进行一次旋转(此时左儿子一定比右儿子高);

③只有右儿子是风铃,这时候维护最大最小深度和判断无解同上,只是不用进行旋转;

④左右儿子都不是风铃,这时候要综合考虑两个儿子来维护最大最小深度。判断无解有两种情况,一是最小深度和最大深度相差超过1,不用解释,二是左右儿子的最大最小深度都不相等,可以自行脑补这种情况也是一定无解的。判断有解后再考虑是否需要旋转即可。

由于树和旋转操作的性质,局部无解=全局无解,所以一遍dfs解决问题。

【代码】

O(n)破解此题O(∩_∩)O~~

http://paste.ubuntu.com/8503919/

评论(1)

© OI技术宅 | Powered by LOFTER