Description

給出一段長(zhǎng)度為\(n\)的整數(shù)序列，求包含所有出現(xiàn)過(guò)的數(shù)的連續(xù)區(qū)間的最小長(zhǎng)度。

Input

第一行給出序列長(zhǎng)度\(n\)，第二行給出\(n\)個(gè)整數(shù)，表示這個(gè)序列。\(n \leqslant 10^6\)。

Output

輸出一個(gè)整數(shù)，表示滿足條件的區(qū)間的最小長(zhǎng)度。

Sample Input

5 1 8 8 8 1

Sample Output

2

Solution

求連續(xù)區(qū)間，尺取問(wèn)題。限制條件是下限，區(qū)間要包含每一種數(shù)。依次推進(jìn)左端點(diǎn)，對(duì)于每個(gè)左端點(diǎn)，右端點(diǎn)向右直到找到第一個(gè)滿足條件的位置，更新答案。如果右端點(diǎn)直到最右端仍然找不到合法區(qū)間，就跳出。

Code

#include <cstdio> #include <cstring> #include <algorithm> #include <map> using namespace std; typedef long long ll; const int INF = 0x3f3f3f3f; const int N = 1e6 + 10;int a[N]; map<int, int> mp;int main() {int n;scanf("%d", &n);mp.clear();for (int i = 1; i <= n; i++) scanf("%d", a + i), mp[a[i]]++;int sum = mp.size();mp.clear();int r = 1, cnt = 0, ans = INF;for (int l = 1; l <= n; l++){while (r <= n && cnt < sum){mp[a[r]]++;if (mp[a[r]] == 1) cnt++;r++;}if (cnt < sum) break;ans = min(ans, r - l);mp[a[l]]--;if (mp[a[l]] == 0) cnt--;}printf("%d\n", ans);return 0; }

Link

http://poj.org/problem?id=3320

轉(zhuǎn)載于:https://www.cnblogs.com/dadamrx/p/7352591.html

總結(jié)

以上是生活随笔為你收集整理的POJ 3320 Jessica's Reading Problem (尺取)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。