算法入门【NC16589】[NOIP2010]机器翻译

思路

Use simulation to solve the problem.
two situations to have access to disk

1. if word is not saved in memeory, read disk
2. if memeory is full, desert the earlist entry element and save the word into last of the memeory.

once u have a try on the problem, i'm convinced that you have found m is still when memeory is full. We can take advantage of it!

so the problem is resolved now. let's code now.

#include<stdio.h>
int memeory[1010];

int main() {
	int m, n, cnt;
  	scanf("%d%d", &m, &n);
  	for(int i = 1;i <= n; i ++ ){
    	int x;
      	scanf("%d",&x);
     	if(memeory[x] != 0) continue;
      	if(m > 0) {
          	memeory[x] = i;
        	m --;
          	cnt ++;
        }
      	else {
        	int min = i, pos = 0;
          	for(int j = 0; j < 1010; ++ j) {
            	if(memeory[j] != 0 && min > memeory[j]){
                	min = memeory[j], pos = j;
                }
            }
          	memeory[pos] = 0;
          	memeory[x] = i;
          	cnt ++;
        }
    }
  printf("%d", cnt);
}

u have some questions about 17-21 lines probably. introductions about them are below. once memeory is full, we have to find the earlist appearing block. so set min to i that is current index and set pos to 0 for recording the value of the word. when we have found them, we should do something about it to exclude the block on 23-25 lines.