关于栈的实现
查看原帖
关于栈的实现
542221
KidA楼主2023/8/8 18:27

对于这份代码,它使用了 STL stack,但是全 RE。

#include<bits/stdc++.h>
#define int long long
using namespace std;

int n,ans;
stack<int> stk;

signed main(){
	ios::sync_with_stdio(0);
	cin>>n; ans=n;
	for(int i=1,d,w;i<=n;i++){
		cin>>d>>w;
		while(!stk.empty()&&stk.top()>w) stk.pop();
		if(stk.top()==w) ans--;
		stk.push(w);
	}
	cout<<ans;
	return 0;
}

改成如下的手写栈后,就可以 AC 了。

#include<bits/stdc++.h>
#define int long long
using namespace std;

int n,ans,top;
int stk[250031];

signed main(){
	ios::sync_with_stdio(0);
	cin>>n; ans=n;
	for(int i=1,d,w;i<=n;i++){
		cin>>d>>w;
		while(top&&stk[top]>w) top--;
		if(stk[top]==w) ans--;
		stk[++top]=w;
	}
	cout<<ans;
	return 0;
}

求助dalao这两份代码为什么相差这么大,感觉思路都一样的啊qwq。

2023/8/8 18:27
加载中...