P1540 机器翻译

思路分析

定义两个一维数组 a[ ]，b[ ] 分别存放文章的所有单词和内存中的单词；设置一个循环遍历文章的所有单词，每个单词有 2 种情况：1、内存中有这个单词；2、内存中没有这个单词；如果内存中有这个单词则不用查找或存入内存，直接进入下次循环；如果内存中没有这个单词则要到词典中查找并存入内存，如果内存未满则直接存入内存，如果内存已满则要删除内存中第一个单词再存入内存；记录下查找的次数即为本题答案；

注意事项

由题可知：对于10%的数据有 M=1，N≤5；对于100%的数据有1≤M≤100，1≤N≤1000；所以数组定义为 a[1003], b[102]；单词存入数组必须按照题目要求存放，不能打乱顺序；

代码实现

#include <stdio.h> int main(){ int M, N; //内存容量和文章长度; int i, j;//循环控制变量; int l = 0, count = 0, flag = 0;//l 表示内存已有单词数，count 记录查找次数，flag 判断内存中是否存在该单词; int a[1003], b[102];//存放文章中的单词和内存中的单词; scanf("%d%d", &M, &N); for(i = 0; i < N; i++) scanf("%d", &a[i]); for(i = 0; i < N; i++){ //判断内存中是否存在该单词; for(j = 0; j < l; j++){ if(a[i] == b[j]){ flag = 1; break; } } if(flag == 1){ flag = 0; continue; } //内存未满，存入内存; else if(l < M){ l++; b[l-1] = a[i]; count++; } //内存已满，删除内存中第一个单词并存入内存; else{ for(j = 0; j < l-1; j++) b[j] = b[j + 1]; b[l-1] = a[i]; count++; } } printf("%d", count); return 0; }