大佬教程收集整理的这篇文章主要介绍了CodeForces - 1173C,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
题意
共2n张牌,有n张空牌与n张标有1-n的数字的牌,现在你手上有n张牌,牌堆里有n张牌,你可以从你手中取一张牌放入牌堆底下,然后取走牌堆顶上的一张牌。求将牌堆中牌以1-n的顺序排列的最小操作次数
思路
分两种情况:
Ⅰ数字1在序列中且直接将牌按顺序
需满足条件:1.数字1在序列中
2.从1开始序列严格递增(check1())
3.轮到任意数字时数字皆在手中(check2())
答案:需加入数字,即n-b[n]
Ⅱ不满足情况Ⅰ
答案:最迟加入1的时间+加入n个数字的时间
#include<bits/stdc++.h> using namespace std; #define ll long long #define M (1000000007) #define N (1000010) int n,mx,ans,a[n],b[n],id[n]; bool out[n]; bool check1(){ for (int i=id[1]+1;i<=n;i++) if (b[i]-b[i-1]!=1) return 0; return 1; } bool check2(){ for (int i=1;i<=id[1]-1;i++) if (b[i]!=0&&b[i]-b[n]<=i) return 0; return 1; } int main(){ scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]),out[a[i]]=1; for (int i=1;i<=n;i++){ scanf("%d",&b[i]); id[b[i]]=i; } if (id[1]!=0&&check1()&&check2()){ printf("%d\n",n-b[n]); return 0; } for (int i=1;i<=id[1];i++) out[i]=1; ans=id[1]; for (int i=id[1]+1;i<=n;i++) if (b[i]!=0) mx=max(mx,(i-id[1])-(b[i]-1)); printf("%d\n",ans+mx+n); }
以上是大佬教程为你收集整理的CodeForces - 1173C全部内容,希望文章能够帮你解决CodeForces - 1173C所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。