90pts,如何卡常?
查看原帖
90pts,如何卡常?
520544
Phrvth楼主2022/8/24 22:42

无语了,90

#include<bits/stdc++.h>

using namespace std;
const int MAXN=2e5+7;
struct node{queue<int> q;}q[MAXN];
int n,a[MAXN],id[MAXN];
vector<int> ans[MAXN];
inline int read(){
	int x=0,f=1;char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
	while(s>='0'&&s<='9') x=x*10+s-'0',s=getchar();
	return x*f;
} 
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0'); 
}
int main()
{
	n=read();
	int last=-1,sum=0,cnt=-1;
	for(int i=1;i<=n+1;i++){
		int x;
		if(i<=n) x=read();
		else x=-1;
		if(x!=last) a[++cnt]=sum,id[cnt]=last,sum=0,last=x;
		sum++;
		q[cnt+1].q.push(i);
	}
	int mnt=0;
	while(cnt>0){
		mnt++;
		for(int i=1;i<=cnt;i++)
			if(a[i]!=0){
				a[i]--,ans[mnt].push_back(q[i].q.front()),q[i].q.pop();
				if(a[i]==0){
					int j=i-1;
					while(j>0&&a[j]==0) j--;
					int k=i+1;
					while(k<=cnt&&a[k]==0) k++;
					if(id[j]==id[k]&&j>=1&&k<=cnt){
						a[j]+=a[k]-1,a[k]=0,ans[mnt].push_back(q[k].q.front()),q[k].q.pop();
						while(!q[k].q.empty())
							q[j].q.push(q[k].q.front()),q[k].q.pop();
					}
				}
			}
		int maxx=0;
		for(int i=1;i<=cnt;i++){
			if(a[i]!=0){
				int j=i-1;
				while(j>=1&&a[j]==0) swap(a[j+1],a[j]),swap(q[j+1],q[j]),swap(id[j+1],id[j]),j--;
				maxx=max(maxx,j+1);
			}
		}
		cnt=maxx;
	}
	for(int i=1;i<=mnt;i++){
		for(int j=0;j<ans[i].size();j++){
			write(ans[i][j]);
			putchar(' ');
		}
		putchar('\n');
	}
	return 0;
}

我用了快读,快输,还是90?

大概思路就是维护一个数组存的是每个块的数量

然后在建一个二维队列吧,(不知道)存他的编号,然后每次取一个,当一个块取完了,就判断相邻两个块的元素是否相同,最后在缩短那个数组的长度

大佬们帮忙看看吧(代码丑

2022/8/24 22:42
加载中...