Uva 11536: Smallest Sub-Array

解題心得

參考網路解法才寫出來。

這題似乎要用到two pointer的概念的變化題。

先假設用一個queue來記錄所有sequence中1~k數字的index，以及countk紀錄當下蒐集到1~k中的總共幾個數字，跟一個array來記錄i最後出現的位置。

每次遇到1~k數字，就先丟進queue中。接著檢查是否第一次遇到這個數字(有沒有在queue中，也就是有沒有在highlight起來的範圍內)，若沒有，則更新countk。最後，我們要檢查highlight範圍左側是不是要變化了，判斷方法是看範圍內的最左側，若去掉該位置，依然能保有1~k的數字，那就可以放棄，一直重覆到不能為止。

那又要怎麼確保會找到最短長度呢？首先我們知道當countk==k時就是一組解，而我們的解法是從頭到尾掃過一次並且動態更新，那麼只要每次都檢查當前的解是否更小即可。

另外我在比較cpe提供的參考解法與網路其他人解法時，一開始不懂為何countk只要++，不考慮--的情況。這是因為只有一開始才是還沒找到解的狀態，只要一找到符合的解，只會不斷解查是不是要更新邊界，但也會確保始終是保持1~k數字的區間。

程式碼 

#include <iostream>
#include <queue>
using namespace std;

int seq[1000001] = { 1,2,3 };

int main()
{
	int T;
	cin >> T;
	for (int round = 1; round <= T; round++)
	{
		int n, m, k;
		cin >> n >> m >> k;

		for (int i = 3; i < n; i++)
			seq[i] = (seq[i - 1] + seq[i - 2] + seq[i - 3]) % m + 1;

		queue<int> q;
		int countK = 0, last_pos[101] = { 0 }, ans = 1000001;
		for (int i = 0; i < 101; i++) last_pos[i] = -1;
		for (int i = 0; i < n; i++)
		{
			if (seq[i] <= k)
			{
				q.push(i);
				if (last_pos[seq[i]] == -1) countK++;
				last_pos[seq[i]] = i;

				while (q.front() != last_pos[seq[q.front()]])
					q.pop();
				if (countK == k)
					ans = min(ans, i - q.front() + 1);
			}
		}
		cout << "Case " << round << ": ";
		if (ans == 1000001) cout << "sequence nai" << endl;
		else cout << ans << endl;
	}
	return 0;
}