社区讨论

【求助】关于时间复杂度

学术版参与者 4已保存回复 6

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@m0degew9
此快照首次捕获于
2024/08/28 13:12
2 年前
此快照最后确认于
2025/11/04 22:12
4 个月前
查看原帖
有没有大佬帮忙分析一下这个程序的时间复杂度啊 qwq。个人感觉是 O(n)O(n) 的,但超时了两个点。
题目是 P7912。
CPP
#include<iostream>
#include<queue>
using namespace std;

const int N=2e5+5;
int n,tot,a[N];
struct Node{ int w,p; };
queue<Node> q[N];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	cin>>n;
	a[0]=-1;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]!=a[i-1]) q[++tot].push((Node){a[i],i});
		else q[tot].push((Node){a[i],i});
	}
	while(1){
		int last=-1,f=0;
		for(int i=1;i<=tot;i++)
			if(!q[i].empty()&&q[i].front().w!=last)
				cout<<q[i].front().p<<' ',
				last=q[i].front().w,
				q[i].pop(),
				f=1;
		cout<<'\n';
		if(!f) break;
	}
	return 0;
}

回复

6 条回复,欢迎继续交流。

正在加载回复...