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

题目描述中已经把大意说的很清楚了~ ### 分析 弦数固定只有六根，然后就是考虑每根弦上的操作：对于每一个音调，必须保证在它前面已经被按下的段落中其段数最大。由此，我们可以考虑**维护六个栈结构，每个栈代表一根弦**。进栈时，**如果栈尾的段数比即将进栈的 j 大，栈尾出栈**，直到栈尾的段数小于等于将要进栈的段数 j，若小于，新段数进栈，若等于，转向下一个要求$(i,j)$。 ~~其实就是一个很直接的模拟啦~~~ 分析完成，接下来上代码！ ### Code ```cpp #include<bits/stdc++.h> using namespace std; int n,p; int a[6][500005],q[6];//a数组代表栈，p数组指向对应的每个栈的栈尾 int ans=0; int main() { scanf("%d%d",&n,&p); int x,y; for(int i=1;i<=n;i++){ scanf("%d%d",&x,&y); x--;//为了节省空间将所有的弦数减一储存 while(a[x][q[x]]>y){//栈尾段数较大的出栈 q[x]--; ans++; } if(a[x][q[x]]<y){//新元素进站（需要动手指呦~） a[x][++q[x]]=y; ans++; } } printf("%d",ans); return 0; } ``` 完结撒fa~