Codeforces Round #310 (Div. 2) C. Case of Matryoshkas

原题: http://codeforces.com/contest/556/problem/C


题目大意: 俄罗斯套娃, 给n个套娃, 套成k组, 每组用数字表示, 大的数字套小的数字, 问怎么把它们套在一起.


分析: 这题想了好久哇. 因为开始读题不仔细, 所以开始想的时候各种WA. 我以为:

1 2 3 4

5 6

这种情况只需要一秒. 但是仔细看题才发现, 这个需要先把6拆下来, 然后把5 套在4上, 然后把6套在5上, 所以是三步. 这个地方卡了好久.

剩下的思路很明确: 首先找到最小的套娃1, 然后往后扫, 看看按照1 2 3 4 ….n这个顺序有几个. 因为把n个套娃套上需要n-1秒,所以坏情况, 就是我们拆下所有的套娃用n-1秒, 然后套上去, 用n-1秒, 这里的-1的原因是编号1的套娃不用动. 所以最坏下是n-1+n-1 = 2n-2秒. 然后我们用排除法, 这里需要把拆开和组装分开记录,一种是 一个链子中为: 1 2 3 4 5 …. 这种情况下, 我用变量b记录了有多少个不用组装的套娃. 第二种是, 不同链子中, 如果最小的套娃不是1, 那么我用变量d记录下来这些要拆开的套娃,对于每个链子d的范围是[0…total(链子长)], 我们都记录一下 所以有d = d + total(链子长) – 1. 但是, 如果链子的最小套娃是1, 那么这些套娃不用被拆开, 所以要d–; 最后的答案是, (n-1) + d(不同链子中套娃,需要拆开总数) – b(组装总数)