程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Codeforces 555A Case of Matryoshkas 套娃娃

Codeforces 555A Case of Matryoshkas 套娃娃

編輯：C++入門知識

Codeforces 555A Case of Matryoshkas 套娃娃

題意：有n個玩具娃娃，編號為1 ~ n。要求一條鏈子上的娃娃必須滿足編號小的娃娃套在編號大的娃娃上。規定兩種操作：1、拆下編號最大的娃娃。2、將一條鏈上的娃娃套在一個沒有套在任何其他鏈子上的娃娃上（有點繞）。意思就是比如有一條鏈1→2→4→5，你可以拆下5，然後變成兩條鏈1→2→4和5，或者將這條鏈套在6上，但是6不能已經套在任何其他鏈子上，變成1→2→4→5→6。題目要求用最少的操作步數將所有的娃娃套在一個鏈子上。

想清楚了其實還是蠻簡單的。每個娃娃最多只需要兩次步驟——拆和套。我們可以這樣想。編號為1的娃娃所在的那條鏈子上，1是不需要拆下來的。也就是不用進行任何操作。如果1套在2上，那麼2也不用拆下來，再接著如果2套在3上，那麼3也不用拆 ...... 以此類推，這條鏈上從1開始連續的數字都是不用拆的。直到某個地方不連續，比如1→2→3→4→6→7→8，其中4套在6上，那麼5肯定在別的鏈子上，需要把6（包括6）以後的所有娃娃都拆下來，然後把5接上去，再把6 7 8接上去。由此看來，這條鏈上從1開始連續的數字不用拆。一旦遇到不連續，則從這個不連續的娃娃開始後面的全部都要拆。對於其他的鏈子，我們設編號最小的娃娃為A，因為它不是1，所以有比它更小的娃娃需要套在A上面，然而題目規定套娃娃的時候A不能已經套在其他的娃娃上，而A又是這條鏈上最小的娃娃，所以這條鏈上除了A以外的娃娃全部都要拆下來。由此看來，其他的鏈子上必須每條鏈子都完全拆卸。而每條鏈子上的最小的娃娃不用拆，但是需要套。對於需要拆的娃娃，必須要操作2次，即拆+套。對於不需要拆但需要套的娃娃，需要操作1次。對於既不用拆也不用套的娃娃，不需要操作。這樣直接計算即可。可以證明這樣肯定是最少的操作步數。一方面，這是至少需要的步數，另一方面，除了從1開始連續的數沒被拆掉，剩下所有的娃娃都被拆成了單個。所以直接按編號順序一個個套即可，不需要多余的步驟，因此這一定是最小步數的操作。

設編號為1的娃娃所在的鏈子上從1開始連續的數字一共有cnt個，那麼答案為2*(n - cnt - (k - 1)) + 1*(k - 1) = 2*(n - cnt) - k + 1即公式。於是我們只需要求出cnt再用公式計算即可。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
using namespace std;

const int MAX = 100005;
int n, k;

void solve()
{
    int m, x, temp, cnt = 1, ans = 2*n - k + 1;
    bool flag;
    while(k--)
    {
        scanf("%d", &m);
        scanf("%d", &x);
        if(x == 1)
            flag = true;
        else
            flag = false;
        temp = x;
        while(--m)
        {
            scanf("%d", &x);
            if(x != temp + 1)
                flag = false;
            if(flag)
                cnt++;
            temp = x;
        }
    }
    printf("%d\n", ans - 2*cnt);
}

int main()
{
    while(scanf("%d%d", &n, &k) != EOF)
        solve();

    return 0;
}