「日常训练」Case of Matryoshkas（Codeforces Round #310 Div. 2 C）

题意与分析（CodeForces 556C）

为了将所有\(n\)个娃娃编号递增地串在一起（原先是若干个串，每个串是递增的），

我们有两种操作：

1. 拆出当前串中最大编号的娃娃（且一定是最右边的娃娃）。
2. 连接一个单个的娃娃（不能和其他娃娃相连着的娃娃）。

问最少操作次数，使得所有娃娃串在一起。

这题当时我是写的相当的痛苦，因为不太擅长这种优雅的思维题QAQ

首先有一点可以知道，如果一串的开头不是1，那么它一定要被整个拆开，操作次数也就是个数-1——这个我花了好久才想到；而如果该串的起点是1，那么它只需要拆后面差值不为1（从那个开始到最后）即可。

然后再算上合并起来的花费即可。

代码

#include <bits/stdc++.h>

#define MP make_pair

#define PB emplace_back

#define fi first

#define se second

#define ZERO(x) memset((x), 0, sizeof(x))

#define ALL(x) (x).begin(),(x).end()

#define rep(i, a, b) for (repType i = (a); i <= (b); ++i)

#define per(i, a, b) for (repType i = (a); i >= (b); --i)

#define QUICKIO                  \

    ios::sync_with_stdio(false); \

    cin.tie(0);                  \

    cout.tie(0);

using namespace std;

using ll=long long;

using repType=ll;

vector<int> mat[100005];

int main()

{

    int n,k; cin>>n>>k;

    vector<pair<int,int> > vec;

    int cnt=0;

    rep(i,0,k-1)

    {

        int m; cin>>m;

        rep(j,0,m-1)

        {

            int tmp; cin>>tmp;

            mat[i].PB(tmp);

        }

    }

    sort(ALL(vec));

    int cocnt=0,ans=0;

    for(int i=0; i<k; ++i)

    {

        rep(j,1,mat[i].size()-1)

        {

            if(mat[i][j]==j+1) ans++;

            else break;

        }

    }

    cout<<(n-1-ans)*2-(k-1)<<endl;

    return 0;

}