Vijos1774 机器翻译 [模拟]

1.题意：给定一段长度为N个单词的文章（一个单词用一个非负整数表示），可以使用一个容量为M个元素的容器。你的任务是使用字典的帮助翻译文章，遇到一个单词，查询之后将此单词的释义放入容器中，下次遇到时若此释义还在容器中就可以不用查字典直接得到结果。当容器已满，再遇到需要进入容器的单词，将容器中最早进入的单词剔除，将当前的单词加入。最后要求给出整个过程中需要查字典的次数。

2.分析：根据题意中容器的描述很容易想到使用队列来实现，同时还需要一个数组inq表示各个单词是否在队列中，一个变量num维护当前队列中的元素数量来决定是否继续push进队还是要pop队首再push

PS：Vijos上M,N的数据范围给反了，若不注意可能一直WA，N应该是N<=1000

代码如下，C++版：

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 # include <queue>
 5 using namespace std;
 6 int inq[1005];
 7 int L[1005];
 8 int M,N;
 9 void Init()
10 {
11     memset(inq,0,sizeof(inq));
12     for(int i=0;i<N;i++)
13         scanf("%d",&L[i]);
14 }
15 void Solve()
16 {
17     int cnt=0;
18     int inqnum=0;
19     queue<int> Q;
20     for(int i=0;i<N;i++)
21     {
22         int temp=L[i];
23         if(inq[temp]) continue;
24         else
25         {
26             cnt++;
27             if(inqnum<M)
28             {
29                 Q.push(temp);
30                 inqnum++;
31                 inq[temp]=1;
32             }
33             else
34             {
35                 int tt=Q.front();
36                 inq[tt]=0;
37                 Q.pop();
38                 Q.push(temp);
39                 inq[temp]=1;
40             }
41         }
42     }
43     printf("%d
",cnt);
44 }
45 int main()
46 {
47     //freopen("in.txt","r",stdin);
48     //freopen("out.txt","w",stdout);
49     while(scanf("%d%d",&M,&N)!=EOF)
50     {
51         Init();
52         Solve();
53     }
54     return 0;
55 }

Python版：

 1 class SQueue():  
 2     def __init__(self,init_len=2):
 3         self._len=init_len
 4         self._elems=[0]*init_len
 5         self._head=0
 6         self._num=0
 7     def is_empty(self):
 8         return self._num==0
 9     def peek(self):
10         #if self._num==0:
11         #    raise QueueUnderflow
12         return self._elems[self._head]
13     def dequeue(self):
14         #if self._num==0:
15         #    raise QueueUnderflow
16         e=self._elems[self._head]
17         self._head=(self._head+1)%self._len
18         self._num-=1
19         return e
20     def enqueue(self,e):
21         if self._num==self._len:
22             self.__extend()
23         self._elems[(self._head+self._num)%self._len]=e
24         self._num+=1
25     def __extend(self):
26         old_len=self._len
27         self._len*=2
28         new_elems=[0]*self._len
29         for i in range(old_len):
30             new_elems[i]=self._elems[(self._head+i)%old_len]
31         self._elems,self._head=new_elems,0
32 while True:
33     try:
34         M,N=map(int,raw_input().split())
35         L=map(int,raw_input().split())
36         inq=[0]*1005
37         cnt=0
38         inq_num=0
39         Q=SQueue()
40         for i in range(N):
41             temp=L[i]
42             #print inq[temp]
43             if inq[temp]==1:
44                 continue
45             else:
46                 cnt+=1
47                 if inq_num<M:
48                     inq_num+=1
49                     inq[temp]=1
50                     Q.enqueue(temp)
51                 else:
52                     tt=Q.dequeue()
53                     inq[tt]=0
54                     Q.peek()
55                     inq[temp]=1
56                     Q.enqueue(temp)
57         print cnt
58     except:
59         break