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(组装总数)

   public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n = in.readInt();// total
        int k = in.readInt(); // num of chains
        int d = 0;// counter for all Matryoskhkas that could be moved in different chains
        int b = 0;// counter for all Matryoskhkas that from 1 to n
        for (int i = 0; i < k; i++) {
            int total = in.readInt();
            d = d + total - 1;
            int p = in.readInt();
            if (p == 1) {
                for (int j = 1; j < total; j++) {
                    p = in.readInt();
                    if (p == j+1){
                        d--;
                        b = j;
                    }
                }
            }
            else {
                for (int j = 1; j < total; j++) {
                    in.readInt();
                }
            }
        }
        out.print(n - 1 + d - b); // result = (total number - 1) + d - b
    }