POJ 3320 - Jessica's Reading Problem

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

概要

P ページの本の各ページが 32bit の符号付き整数に収まる数字で表されている． 本のすべての内容を含んでいるような連続したページで，最小の長さを答える．

制約

• 1 <= P <= 1000000

解法

最初に map につっこんで数字を正規化しつつ何種類あるのか数えておいて，しゃくとりメソッド的なかんじで先頭から見ていく．

 1 #include <cstdio>
 2 #include <map>
 3 using namespace std;
 4 
 5 int numbering(map<int,int>& m, int x)
 6 {
 7   const map<int,int>::const_iterator it = m.find(x);
 8   if (it != m.end()) {
 9     return it->second;
10   } else {
11     const int n = m.size();
12     m.insert(make_pair(x, n));
13     return n;
14   }
15 }
16 
17 int main()
18 {
19   int P;
20   scanf("%d", &P);
21   static const int M = 1000000;
22   static int ids[M];
23   map<int,int> m;
24   for (int i = 0; i < P; i++) {
25     int x;
26     scanf("%d", &x);
27     ids[i] = numbering(m, x);
28   }
29   const int size = m.size();
30   static int cnt[M];
31   const int *last = ids + P;
32   const int *end = ids;
33   for (int n = 0; end != last && n < size; ++end) {
34     if (cnt[*end] == 0) {
35       ++n;
36     }
37     ++cnt[*end];
38   }
39   const int *begin = ids;
40   while (cnt[*begin] > 1) {
41     --cnt[*begin];
42     ++begin;
43   }
44   int ans = end - begin;
45 
46   for (; end != last; ++end) {
47     ++cnt[*end];
48     while (cnt[*begin] > 1) {
49       --cnt[*begin];
50       ++begin;
51     }
52     ans = min(ans, int(end - begin + 1));
53   }
54   printf("%d\n", ans);
55   return 0;
56 }