洛谷P1160题解

洛谷P160

题目简述：

按照学生编号输入学生，每次要查到已有学生的左面或者右面，还要进行删除操作。
数据规模maxn高达100000

题目分析

1.看到这到题目就是插入删除操作，信心满满的写了一个的链表，却喜提RE

#include<cstdio>

const int maxn = 100000 + 5;
int nex[maxn];
int n;

int main() {
	scanf("%d", &n);
	nex[0] = 1; nex[1] = 0;
	int loc, v;
	for (int i = 2; i <= n; i++) {
		int cur;
		scanf("%d%d", &v, &loc);
		if (loc == 0) {//找插入点
			cur = 0;
			while (nex[cur] != v) {
				cur = nex[cur];
			}
		}
		else if (loc == 1) {
			cur = v;
		}

		nex[i] = nex[cur];//插入
		nex[cur] = i;
	}

	int m,d;
	scanf("%d", &m);

	for (int i = 0; i < m; i++) {
		scanf("%d", &d);
		int cur = 0;
		int is_find = 1;
		while (nex[cur] != d) {
			cur = nex[cur];
			if (cur == 0) {
				is_find = 0;
				break;
			}
		}
		if(is_find)nex[cur] = nex[d];
	}

	int cur = nex[0];
	while (cur != 0) {
		printf("%d ", cur);
		cur = nex[cur];
	}
	printf("\n");
	return 0;
}

反思优化：

想了一下，如果每次找元素都从都开始扫时间复杂度是n平方，10的五次方的情况下确实会超时

下面使用了双向链表来改良，每次插入查到左面就用pre，插到后面就用nex，时间复杂度变成O(n)

#include<cstdio>

const int maxn = 100000 + 5;
int nex[maxn], pre[maxn];
int is_delete[maxn];
int n;

int main() {
	scanf("%d", &n);
	nex[0] = 1; nex[1] = 0;
	pre[1] = 0; pre[0] = 1;
	int loc, v;
	for (int i = 2; i <= n; i++) {
		scanf("%d%d", &v, &loc);
		if (loc == 0) {//找插入点
			int memo = pre[v];
			pre[v] = i; pre[i] = memo;
			nex[memo] = i; nex[i] = v;
		}
		else if (loc == 1) {
			int memo = nex[v];
			nex[v] = i; nex[i] = memo;
			pre[memo] = i; pre[i] = v;
		}
	}

	int m,d;
	scanf("%d", &m);

	for (int i = 0; i < m; i++) {
		scanf("%d", &d);
		is_delete[d] = 1;
	}

	int cur = nex[0];
	while (cur != 0) {
		if(!is_delete[cur])printf("%d ", cur);
		cur = nex[cur];
	}
	printf("\n");
	return 0;
}

最后