Codeforces #310ACase of Matryoshkas（模拟）

54 阅读 0 评论 36 点赞

我是靠谱客的博主无情汽车，最近开发中收集的这篇文章主要介绍Codeforces #310ACase of Matryoshkas（模拟），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

【题目链接】click here~~

【题目大意】给你n个玩具，规定只能小的玩具套在大的上面，而且是规格依次递增的，比如：1->2->3，求所有玩具套完需要的最小时间花费

【解题思路】：只能怪CF时间太晚了，本来前一天熬夜，精神有点疲劳，这次第一题还是赛后补做的，哎~~只能说太虚~~

我的做法：找到序列为1 的，然后依次判断后面的

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=1e6;
int num[N];
int n,m,k,t,ans,cnt,res,top;
int pre,last,len;
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        int h1=0,res=0;
        int q,o,ans;
        bool ok=0;
        while(m--)
        {
            scanf("%d",&q);
            for(int i=1; i<=q; ++i)
            {
                scanf("%d",&num[i]);
                if(num[i]==1)
                {
                    ok=1;
                }
            }
            if(ok)
            {
                h1=1;
                for(int i=2; i<=q; ++i)
                {
                    if((num[i])==(num[i-1]+1))
                        h1++;
                    else break;
                }
                res+=q-h1;
                ok=0;
            }
            else
            {
                res+=q-1;
            }
        }
        res+=n-h1;
        printf("%dn",res);
    }
    return 0;
}

看到别人的一种做法：

思路比较清晰，拿过来借鉴一下~~

/*
res:记录最长满足条件即单调递增序列的长度
(n-m-res+1)：每组玩具假设全部拆解需要的时间
(n-res)：全部玩具重新套上的时间
*/
#include <bits/stdc++.h>
using namespace std;
const int N=1e6;
int num[N];
int n,m,k,t,ans,cnt,res,top;
int pre,last,len;
int main()
{
    cin>>n>>m;
    res=0;
    for(int i=0; i<m; ++i)
    {
        cin>>k;
        last=len=0;
        for(int i=0; i<k; ++i)
        {
            cin>>num[i];
            if(num[i]==last+1)
            {
                last++;
                len++;
            }
        }
        res=max(res,len);
    }
    printf("%dn",(n-m-res+1)+(n-res));
}
/*
input
3 2
2 1 2
1 3
output
1
input
7 3
3 1 3 7
2 2 5
2 4 6
output
10
input
7 3
3 1 2 7
2 3 5
2 4 6
output
8
*/