修改數組

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;
}