蓝桥杯高频考点真题单——4.修改数组

修改数组

8.修改数组 - 蓝桥云课 (lanqiao.cn)

本来我的思路很一般，用一个set，记录每一段的最值，然后分情况讨论，如果查询到未记录的，那就直接输出，并记录。如果当前值前面已经有过，那就直接从set中调出首个比他大的值，就是该段最值（下面我称之为大哥）。

错误思路：

for (int i = 0; i < n; i++)
{
	cin >> a;
	if (book[a] == 0)	//如果没有标记过
	{
		if (book[a - 1] == 0 && book[a + 1] == 0)	//单独作为大哥
		{
			book[a] = 2;
			prime.insert(a);
		}
			
		else if (book[a - 1] == 2 && book[a + 1] == 0)	//在其他大哥之前
		{
			book[a - 1] = 1;
			book[a] = 2;

			prime.erase(a - 1);
			prime.insert(a);
		}
		else if(book[a - 1] == 0 && book[a + 1] != 0)  //接在屁股后面，不管他
			book[a] = 1;
		cout << a << " ";	//没标记过，说明之前无值，直接输出
	}
	else //之前标记过
	{
		int bro = getPrime(a);	//找到大哥
		book[bro + 1] = 2;		//更新大哥
		book[bro] = 1;
		prime.erase(bro);
		prime.insert(bro + 1);
		cout << bro + 1 << " ";	//输出新大哥
	}
}

上面的思路我觉得问题在于情况的讨论，而且大数据下也无法验证其准确性。还是老老实实用并查集吧。

什么时候用并查集？当你需要大哥的时候。思路和上面类似，值得注意的是，因为本题的集合是线段，而不是图，所以join函数根本没用，但是为了让大家对并查集的整体认知，还是写在代码中，可以自行删除。

还有就是需要一定程度上进行优化。

AC：

#include <iostream>
using namespace std;

// 其实在我写第一个set的时候，就已经有种超级熟悉的感觉了，并查集，找大哥

const int N = 1e6 + 3;
int n;
int pre[N];

void init()
{
	for (int i = 0; i <= N; i++)	pre[i] = i;
}

int find(int a)
{
	/*  会超时，这里优化一下find，让她直接指向大哥
	while (pre[a] != a)
		a = pre[a];
	return a;*/

	int root = a;
	while (pre[root] != root)	root = pre[root];

	int fa = pre[a];
	while (fa != root)
	{
		pre[a] = root;
		a = fa;
		fa = pre[a];
	}
	return root;
}

//join可以删除
void join(int a, int b)
{
	int fa = find(a);
	int fb = find(b);
	if (fa != fb)	pre[fa] = fb;
}


int main()
{
	init();
	cin >> n;
	int a;
	for (int i = 0; i < n; i++)
	{
		cin >> a;
		a = find(a);
		cout << a << " ";
		pre[a] = a + 1;
	}

	return 0;
}