首页 > 代码库 > Codeforces 821C Okabe and Boxes(模拟)

Codeforces 821C Okabe and Boxes(模拟)

题目大意:给你编号为1-n的箱子,放的顺序不定,有n条add指令将箱子放入栈中,有n条remove指令将箱子移除栈,移出去的顺序是从1-n的,至少需要对箱子重新排序几次。

解题思路:可以通过把栈清空表示已经排过序了,如果下一次remove时栈为空,说明已经排序过且没有新的箱子放入,因为题目确保在需要删除之前添加每个箱子,所以肯定栈顶的箱子是我们所需要的。如果栈不为空则判断栈顶箱子序号是否是我们需要的,不是则重新排序,用清空栈来表示。

这里用数字模拟了栈。

 1 #include<iostream>
 2 using namespace std;
 3 
 4 const int N=3e5+5;
 5 
 6 int a[N];
 7 
 8 int main(){
 9     int n,len=0,pre=0,ans=0;
10     cin>>n;
11     for(int i=1;i<=n*2;i++){
12         char s[10];
13         cin>>s;
14         if(s[0]==a)
15             cin>>a[++len];
16         else{
17             if(len==0);
18             //清空栈 
19             else if(a[len]==pre+1) len--;
20             else len=0,ans++;
21             pre++;
22         }
23     }
24     cout<<ans<<endl;    
25 }

 

Codeforces 821C Okabe and Boxes(模拟)