d892 - NOIP2010 1.机器翻译

🔗 前往 ZeroJudge 原題

題目描述

題目描述了一個機器翻譯軟體的行為。給定記憶體容量 M 和文章長度 N，以及文章中每個單字的數值表示。程式需要計算翻譯軟體需要查詢詞典的次數。如果單字在記憶體中已存在，則直接翻譯；否則，查詢詞典，並將單字和譯義存入記憶體。如果記憶體已滿，則替換最早進入記憶體的單字。

解題思路

這題可以使用一個固定大小的陣列來模擬記憶體。遍歷文章中的每個單字，檢查該單字是否已在記憶體中。如果在記憶體中找到，則不進行任何操作。如果未找到，則查詢詞典（計數器加一），並將單字添加到記憶體中。如果記憶體已滿，則替換最早加入記憶體的單字。使用取模運算符 % 可以輕鬆實現替換最早加入記憶體的單字的功能。

複雜度分析

• 時間複雜度: O(N * M)
• 空間複雜度: O(M)

程式碼

#include <stdio.h>
int main(){
	int a,b,ans=0,t=0,n;
	scanf("%d%d",&a,&b);
	int c[a];
	for(int i=0,chat=0;i<b;i++,chat=0){
		scanf("%d",&n);
		for(int j=0;j<t&&j<a;j++){
			if(c[j]==n){
				chat=1;
				break; 
			}
		}
		if(chat==0){
			ans++;
			c[t%a]=n;
			t++;
		} 
	}
	printf("%d",ans);
}