[筆記] Codeforces 1208B: List Of Integers

[題意] 給一個正整數 n ($1 \leq n \leq 2000$) ，後面接著 n 正整數 $a_1, a_2, ... , a_i, ..., a_n$ ($1 \leq a_i \leq 10^9$)，請找出一個這數列的一段連續區間使得這 n 個數字拿掉這段區間後的數字皆不重複。答案要找的是這段區間最小的長度是多少

原題目中有給例子的解說，最下面的實作其實裡面也有多放一點例子當作參考，這邊就先跳過直接講概念吧

首先從 2 個面相來看這題

• 一個數字有沒有重複出現：丟進 std::set 或 std::unordered_set 裡很快就能知道
• 刪掉的區間中要包含所有重複出現的數字：從最左邊開始往右掃，出現重複的數字就停；再從最右邊往左邊掃，出現重複的數字就停，這兩個端點夾住的數字全刪了就一定不會有重複的數字

所以要刪掉重複的數字很簡單，但是要怎樣才有可能讓這段區間更短？這可以從一張圖來看

以這 10 個數字來看，藍色線條是方便看出那些數字有重複以及他所在的區間，綠色的 { 所標示的範圍就是用上面提到最直接的想法所標示出的答案。但從這些數字我們可以發現其實最短的區間是紅色的 { 所標示的範圍，因為這個範圍確實地把所有重複數字都囊括進來了！而紅色 { 的範圍跟綠色 { 的範圍差異其實可以這樣看：

從左邊往右掃到第一個重複出現數字時會讓右邊更容易掃到重複的數字

所以換個方向想：先從右邊往左掃到第一個重複出現的數字、再從左邊往右掃到重複出現的數字答案是不是會不一樣呢？

沒錯! 確實是會不一樣，以上圖中的數字來看，先從右邊掃就可以得到紅色 { 的範圍了。

再更進一步想，有沒有可能兩邊同時掃才能得到更短的區間的例子？

沒錯，確實有！考慮序列 1 2 3 4 5 10 1 6 7 8 9 10，最短的區間是正中間的 10 1，但不論從左邊先掃或從右邊先掃都不會找到正中間的這段區間。

所以如果用更一般化的方式來思考這問題的話，不論先從哪個方向開始掃都有可能會因為有先掃後查的問題導致找到的區間無法進一步縮短，那該怎麼辦？其實就是再往回掃去看看是不是有更短的就好

1. 先固定從一邊掃到重複的數字 (假設先從左邊往右掃)
2. 再從反方向掃到重複出現的數字 (承上，所以就是從右往左掃)
3. 解放 1.找到的邊界並且往 2. 的移動方向移動，並且試試看是否能讓 2. 的端點往 1. 的端點移動從而縮短區間。(以這邊的例子就是讓 1. 找到的左邊界往左移，看看右邊界能不能一口氣往左邊移動)
4. 重複 3. 的動作直到再也不可能移動區間了

3. 的重點其實就是讓原本因為先從左往右掃的過程中因為找到重複的數字而讓右邊的區間被固定了，現在因為被移除了而可以大舉往左移動。

最後一點要注意的應該就是要算清楚區間長度跟被釋放的數字哪一個數字了，這大概就是解這一題需要頭腦最清楚的地方...


實作如下：

	/*
	* =====================================================================================
	*
	* Filename: 1208B.cpp
	*
	* Description: codeforces 1208B: Uniqueness
	*
	* Version: 1.0
	* Created: 2019年08月31日
	* Revision: none
	* Compiler: gcc
	*
	* Author: lionking
	* Organization: None
	*
	* =====================================================================================
	*/
	// possible cases:
	// case 1:
	// 10
	// 7 7 7 1 2 3 4 5 6 7
	// answer: 3 (first 3 digits: 7 7 7)
	//
	// case 2:
	// 10
	// 1 2 3 4 3 4 5 6 7 1
	// answer: 4 (first 4 digits: 1 2 3 4)
	//
	// case 3:
	// 9
	// 1 9 2 9 0 1 5 5 3
	// answer: 4 (digit sequence: 9 0 1 5)
	//
	// case 4:
	// 3
	// 1 2 3
	// answer: 0 (no digit needs to be removed)
	//
	// case 5:
	// 10
	// 1 9 2 9 0 1 5 5 3 9
	// answer: 6 (digit sequence: 9 2 9 0 1 5)
	#include <cstdio>
	#include <unordered_set>
	using namespace std;
	int main()
	{
	constexpr int NUM_SIZE = 2001;
	int n, num[NUM_SIZE];
	unordered_set<int> exist;
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
	scanf("%d", num+i);
	}
	int lidx = 1;
	for (; (lidx <= n) && (exist.count(num[lidx]) == 0); ++lidx) {
	exist.emplace(num[lidx]);
	}
	auto result = n;
	int ridx = n;
	for (--lidx; lidx >= 0; --lidx) {
	for (; (ridx > 0) && (exist.count(num[ridx]) == 0); --ridx) {
	exist.emplace(num[ridx]);
	}
	result = min(result, ridx - lidx);
	exist.erase(num[lidx]);
	}
	printf("%d\n", result);
	return 0;
	}

view raw codeforces-1208B.cpp hosted with ❤ by GitHub