链表代码
查看原帖
链表代码
428690
Astatinear楼主2021/11/1 13:23

这个代码不知道为什么会出现死循环,我自己hack不掉 (就是有8,9两个点TLE)

求hack

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<climits>
using std::vector;
using std::cin;
int n;
int a[300005];
int cnt;
struct node
{
	vector<int> pq;
	int l,r;
	int bj;
}edge[300005];
int vis[300005][3];
int main()
{
	cin>>n;
	for(int i=1;i<=n;++i)
	{
		cin>>a[i];
		edge[i].bj=-1;
	}
	a[0]=INT_MAX;
	edge[0].bj=INT_MAX;
	for(int i=1;i<=n;++i)
	{
		if(a[i]!=a[i-1])
		{
			cnt++;
			edge[cnt].pq.push_back(i);
			edge[cnt].bj=a[i];
			edge[cnt].r=1,edge[cnt].l=1;
			vis[cnt][0]=cnt-1;
			vis[cnt][1]=cnt+1;
		}
		else
		{
			edge[cnt].pq.push_back(i);
			edge[cnt].r++;
		}
	}
	edge[cnt+1].bj=INT_MAX;
	vis[cnt][1]=0;
	vis[0][1]=1;
	while(1)
	{
		bool ch=0;
		for(int i=vis[0][1];i;i=vis[i][1])
		{
			if(edge[i].l>edge[i].r)
			{
				int head=vis[i][0],tail=vis[i][1];
				vis[head][1]=tail;
				vis[tail][0]=head;
			}
		}
		for(int i=vis[0][1];i;i=vis[i][1])
		{
			int x=edge[i].pq[edge[i].l-1];
		    if(edge[vis[i][0]].bj!=edge[i].bj)
		    {
		    	edge[i].l++;
		    	ch=1;
				printf("%d ",x);
			}
		}
		if(ch==0)
		break;
		printf("\n");
	}
	return 0;
}

2021/11/1 13:23
加载中...