本文共 887 字，大约阅读时间需要 2 分钟。
1 /* 2 尺取法：先求出不同知识点的总个数tot，然后以获得知识点的个数作为界限， 更新最小值 3 */ 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 using namespace std;11 12 const int MAXN = 1e6 + 10;13 const int INF = 0x3f3f3f3f;14 int a[MAXN];15 16 int main(void) //POJ 3320 Jessica's Reading Problem17 {18 int n;19 while (scanf ("%d", &n) == 1)20 {21 set S;22 for (int i=1; i<=n; ++i)23 {24 scanf ("%d", &a[i]); S.insert (a[i]);25 }26 27 map cnt;28 int tot = S.size (); int ans = n, num = 0; int i = 1, j = 1;29 while (1)30 {31 while (j <= n && num < tot) if (cnt[a[j++]]++ == 0) num++;32 if (num < tot) break;33 ans = min (ans, j - i);34 if (--cnt[a[i++]] == 0) num--;35 }36 37 printf ("%d\n", ans);38 }39 40 return 0;41 }
转载于:https://www.cnblogs.com/Running-Time/p/4550274.html