C. Nauuo and Cards

原题链接:http://codeforces.com/contest/1173/problem/C

题目大意 :有2n张卡片,其中n张编号为1-n,另外n张为0. 现在手中拿n张,桌子上放n张,每次操作可以在桌子上底部放入一张卡片,最上面拿走一张卡片,问最小操作次数。

思路: 先看看卡片1的位置,卡片1在桌子上时,看看是否满足从1递增到底部,例如 0 0 1 2 3 4 。如果满足就依次插入卡片,取出卡片。 

   如果1在手中,就开始依次插入卡片,取出卡片,从1开始,插入1之后,如果2卡片此时仍然在桌子上的卡组里,操作次数+1,取出最前面的卡片,继续判断2卡片。(这里意思是如果2不在手里,就要等2拿到之后再插入,相当于在1卡片的前面插入了0卡片,即1卡片插入的次数延后)

代码如下:

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <string>
 5 #include <cstring>
 6 #include <cmath>
 7 #define ll long long
 8 using namespace std;
 9 int a[200005],b[200005],c[200005];
10 int main ()
11 {
12     int i,t,m,n,u,sum=0,maxs,mins,x,y=0,z;
13     scanf("%d",&n);
14     for(i=1;i<=n;++i){
15         scanf("%d",&t);
16         a[t]++; 
17         c[t]++; //a,c数组记录手中的卡牌 
18         }
19     for(i=1;i<=n;++i)
20         scanf("%d",&b[i]);
21     int j,k;
22     if(a[1]==0) //判断1在不在手中
23     {
24         for(i=1;i<=n;++i)
25             if(b[i]==1)
26         {
27             k=1;j=1;
28             while(j) // 1在桌子上的卡组时,判断1后面是否依次递增到最后一张
29             {
30                 if(i==n)
31                 {
32                     break;
33                 }
34                 else
35                 {
36                     i++;
37                     k++;
38                     if(b[i]!=k)
39                     {
40                         j=0;
41                     }
42                 }
43             }
44             if(!j)
45                 break;
46         }
47     }
48     k=0;
49     if(j) //如果从卡片1到最后一张都是依次递增的,判断能否继续往后添加卡片
50     {
51         x=b[n]+1;
52         if(x-1==n) //如果正好桌上的牌满足1-n递增放好
53             k=1;
54         for(i=1;i<=n;++i){
55             if(c[x]==1)
56                 sum++;
57             else {
58                 break;
59             }
60             c[ b[i] ]++; //取出最前面的卡片
61 
62             if(x>=n) //顺利放完全部卡片
63                 k=1;
64             x++;
65         }
66     }
67     if(k){
68         printf("%d\n",sum);
69         return 0;
70     }
71   //如果卡片1在手中
72     sum=0;
73     int p=1;
74     for(i=1; ;++i)
75     {
76         if(a[p]==1) //将卡片p放入,如果此时卡片p不存在,操作数+1 ,取出最前面的卡片 (相当于在卡片1前面插入一张0卡片)
77             p++;
78 
79         a[ b[i] ]++; //取出最前面的卡片
80         sum++; //记录操作次数
81         if(p==n+1)
82             break;
83     }
84     printf("%d\n",sum);
85 
86     return 0;
87 }

 

上一篇:注意力机制SimAM(SimAM: A Simple, Parameter-Free Attention Module for Convolutional Neural Networks)


下一篇:PyTorch 卷积神经网络(Convolutional Neural Network)