打表-(POJ)机器翻译

╰+哭是因爲堅強的太久メ 2022-05-18 06:53 193阅读 0赞

*  # 打表-(POJ)机器翻译 #

--------------------

题目链接：[机器翻译][Link 1]

*  ## 思路 ##

看了下题目数据的范围，百万级，如果定义队列然后每输入一个单词去查找是否存在，耗费的时间巨大

所以定义一个布尔类型数组，初始化false（表示元素不存在内存）

当输入一个单词，**如果存在内存中，那么不做任何操作**

如果**不存在内存**，那么按题目要求是**该单词入队**，**如果队满弹出队头再入队**

**出队单词在布尔数组中需要重置****false****，而入队置****true**

众所周知普通数组队列在一系列出队入队后实际的队列容量会减小

为了避免这种情况，本题使用了***循环队列***

*  ## 代码 ##

#include<iostream>
    #include<cstdio>
    using namespace std;
    //算法与数据结构Mooc（第三章栈与队列11机器翻译
    bool Memory_Record[1000005] = { 0 };
    
    int main()
    {
    	int *Model_Queue;
    	int Front = 0, Rear = 0;
    	int MAX_SIZE, Check_Time, Word;
    	int Find_Time = 0;
    	//cin >> MAX_SIZE >> Check_Time;
    	scanf("%d%d", &MAX_SIZE, &Check_Time);
    	MAX_SIZE++;							//+1的原因是循环队列具有一个单元的缓冲空间
    	Model_Queue = new int[MAX_SIZE];
    	while (Check_Time--)
    	{
    		
    		//cin >> Word;
    		scanf("%d", &Word);
    		if (Memory_Record[Word])		//find
    			continue;
    		if ((Rear + 1) % MAX_SIZE == Front)		//full
    		{
    			Front = (Front + 1) % MAX_SIZE;    //pop
    			Memory_Record[Model_Queue[Front]] = false;    //修改该单词为不存在内存中
    		}
    		Memory_Record[Word] = true;   //新入队单词标记为存在
    		Rear = (Rear + 1) % MAX_SIZE;
    		Model_Queue[Rear] = Word;
    		Find_Time++;
    	}
    	//cout << Find_Time << endl;
    	printf("%d\n", Find_Time);
    	return 0;
    }

[Link 1]: http://dsalgo.openjudge.cn/stackqueue/11/