思路还是很明朗的,但是答案就是不对。。?
查看原帖
思路还是很明朗的,但是答案就是不对。。?
122342
今夕何年楼主2022/5/19 13:22
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<limits.h>
#include<algorithm>
#include<iomanip>
#include<stack>
using namespace std;

int n,p; 
int **datas;
int last_index[7];
int ans=0;

int counts(int x){//对第x根弦上的次数进行统计
	int ct=0;
	stack<int>s;
	while(!s.empty()){
		s.pop();
	}//初始化,清空栈
	for(int i=1;i<=last_index[x];++i){
		int xx=datas[x][i];//当前要弹奏的音符
		if(!s.empty() && s.top()==xx)continue;//栈顶音符和这个音符一致,不需要入栈 
		if(s.empty() || (!s.empty() && s.top()<xx)){//入栈条件,维护栈顶到栈底降序 
			s.push(xx);
			++ct; 
		}else{
			while(!s.empty() && s.top()>xx){
				s.pop();
				++ct;
			}
			if(!s.empty() && s.top()==xx)continue;
			else{
				s.push(xx);
				++ct;
			} 
		}
	}
	return ct;
}


int main(){
	cin>>n>>p;
	datas=new int*[7];
	for(int i=0;i<7;++i){
		datas[i]=new int[p+1];
	}
	//产生data[i][j],记录第i根弦,第j个音符
	int number;
	for(int i=1;i<=n;++i){
		cin>>number>>datas[number][++last_index[number]];//last_index[i]记录第i根线的音符个数
	}
	for(int i=1;i<=6;++i){
		ans+=counts(i);
	}
	cout<<ans;
	return 0;
}

维护一个从栈顶到栈底单调递减的栈,pop或者push就++ans

2022/5/19 13:22
加载中...