TLE on#8#9,80分怎么优化
查看原帖
TLE on#8#9,80分怎么优化
930325
Li_Yichen楼主2024/4/16 21:51

感觉跑不满 O(n2)O(n^2) 啊

#include<bits/stdc++.h>
using namespace std;
int n;
int a[200005];
struct Block{
	int l,r;
	int data;
};
vector<Block> tmp;
queue<Block> q;
int sum;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> a[i];
	}
	int len = 0;
	for(int i=1;i<n;i++){
		if(a[i] != a[i+1]){
			q.push((Block){i-len,i,a[i]});
			len = 0;
		}else len ++;
	}
	q.push((Block){n-len,n,a[n]});
	sum = q.size();
	while(sum != 0){
		tmp.clear();
		int last = !(q.front().data);
		while(!q.empty()){
			Block now = q.front();
			q.pop();
			if(last != now.data){
				//q.pop();
				cout << now.l << " ";
				now.l ++;
				int len = now.r - now.l + 1;
				if(len > 0){
					tmp.push_back((Block){now.l,now.r,now.data});
					//cout << now.l << " " << now.r << " " << now.data << " last:" << last << endl;
				}
			}else tmp.push_back((Block){now.l,now.r,now.data});
			last = now.data;
		}
		cout << endl;
		for(int i=0;i<tmp.size();i++){
			q.push(tmp[i]);
			//cout << tmp[i].l << " " << tmp[i].r << " " << tmp[i].data << endl;
		}
		//cout << "------------------------" << endl;
		sum = q.size();
	}
	return 0;
}

2024/4/16 21:51
加载中...