求助 样例都过不了
查看原帖
求助 样例都过不了
497711
EnriqueYXH楼主2021/10/29 20:27

把每个块用 链表串起来 不知为何会输出n之外的数

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
typedef long long LL;
inline int read() {
	int x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {if (ch == '-') f = -1;ch = getchar();}
	while (ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
	return x * f; 
}
const int N = 1e6 + 5;
int n, x;
struct PPP{
	int len, v, num; // num 为 头的位置  
}p[N];
struct link{
	int l, r;
}e[N];// 链表存储 前后块的位置 
int cnt;
vector <int> v;
int main() {
	n = read();
	int last = 1;
	for (int i = 1; i <= n; i++) {
		x = read();
		if (i == 1 || x != last) {
			p[++cnt].len = 1;
			p[cnt].v = x;
			p[cnt].num = i;
		}
		else {
			p[cnt].len++;
		}
		last = x;
	}
	if (cnt == 1) e[1].l = e[1].r = -1;
	else {
		e[1].l = -1, e[1].r = 2;
		e[cnt].l = cnt - 1, e[cnt].r = -1;
	}
	for (int i = 2; i < cnt; i++) {
		e[i].l = i - 1, e[i].r = i + 1;
	}
	int hh = 1;
	while (hh != -1) {
		for (int i = hh; i != -1; i = e[i].r) {
			printf("%d ", p[i].num++);
			p[i].len--;
		}
		for (int i = hh; i != -1; i = e[i].r) {
			if (!p[i].len) {
				if (i == hh) hh = e[hh].r;
				int ll = e[i].l, rr = e[i].r;
				if (ll == -1 || rr == -1) {
					if (ll == -1 && rr == -1) continue;
					if (ll == -1) e[rr].l = -1;
					else e[ll].r == -1;
				}
				else {
					if (p[ll].v != p[rr].v) 
						e[ll].r = rr, e[rr].l = ll;
					else {
						e[e[ll].l].r = rr;
						e[rr].l = e[ll].l;
						p[rr].len += p[ll].len;
						p[rr].num = p[ll].num;
					}
				}
			}
		}
		cout << endl;
	}
	return 0;
}
2021/10/29 20:27
加载中...