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

· · 题解

观前提示

博客食用更加

题目传送门

这题可以利用栈的思想

将每一种弦都用一种栈（本人太蒟，不会用STL）

如果有数进来时

就和栈顶比较大小

如果栈顶>进来的数

就要出栈

注意：

当 1\quad 5\quad 1\quad 6\quad 1\quad 5 时，虽然已经按过 1\quad 5，但是也要先松开 1\quad 6 的键，然后可以不用按 1\quad 5 （用其他方法的小朋友们！敲黑板！做笔记！）

接下来是AC代码（有注释）

#include<iostream>
#include<cstdio>
using namespace std;
int n,p,x,y,s,sum[7],a[7][300005];
int main()
{
    scanf("%d%d",&n,&p);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&x,&y);
        while(sum[x]>=1&&a[x][sum[x]]>y)//判断栈是否空，还有比较栈顶
        {
            sum[x]--;//减减
            s++;//累加次数  
        }
        if(a[x][sum[x]]==y)continue;//如果与栈顶相同就跳过
        a[x][++sum[x]]=y;//入栈
        s++;//累加次数
    } 
    printf("%d",s);//输出次数
    return 0;
}

谢谢