题解 P6704 【[COCI2010-2011#7] GITARA】

Daidly · 2020-10-07 11:51:17 · 题解

更好的阅读体验

【不会栈的可以先看看这个】

这道题的标签是栈，所以这篇代码是STL的栈。

先讲一下思路：

• 我们可以用一个栈来储存一个弦的各个段，记为stack<int>s[7];因为有6个弦。

• 因为可能有一个音调要可松开多次，所以用一个while循环，每一次循环弹出栈顶，其条件为栈不为空和栈顶值大于段号。

• 特判当栈顶与段号相同时，直接跳过。

• 注意：不能直接写if(s[a].top()==b)，要提前特判栈中有没有值，如果没有的话，这样做会报错。

#include<bits/stdc++.h>
using namespace std;
int n,p,a,b,ans=0;
stack<int>s[7];
int main(){
    cin>>n>>p;
    for(int i=1;i<=n;++i){
        cin>>a>>b;
        while(s[a].size()>0&&s[a].top()>b){
            ans++;
            s[a].pop();
        }
        if(s[a].size()>0){
            if(s[a].top()==b){
                continue;
            }else{
                ans++;
                s[a].push(b);
            }
        }else{
            ans++;
            s[a].push(b);
        }
    }cout<<ans;
    return 0;
}

希望通过，谢谢！