Description
栗酱在上操作系统原理这门课。
她遇到了一个内存管理的置换策略上的问题。
问题可以简化成,有一个单线程程序,有nn步执行,每步执行需要调用第a_iai个数据。不同的数据的大小相同。根据数据的大小,你被分配了mm页内存,每页内存可以装取一个数据。
一开始所有的数据都在硬盘(虚拟内存)里存储。当程序需要调用第a_iai个数据的时候,栗酱的老爷机需要使用整整11秒钟把内存的数据移出,再从硬盘里读出数据,并覆盖写入到某一格内存中。
程序在每步执行过程中,需要调用的数据在内存中,位置不限,如果不在内存中,则花费时间需要从硬盘中读入。
栗酱打算使用实现简单的FIFO(先入先出)策略,即当内存不够放的时候,优先把最早进来的删掉,具体请参见样例。
问按照栗酱采用的策略,在内存管理的置换上需要耗费多少时间。
Input
第一行为数据组数TT( T\le1000T≤1000 )。
每组数据第一行输入两个整数N,MN,M,分别代表程序的执行步数和被分配的内存的页数。
1 \le N,M,a_i\le 1000001≤N,M,ai≤100000
每组数据第二行包含NN个整数,a_iai表示第ii步需要的数据。
数据保证\sum N\le 2,000,000∑N≤2,000,000
Output
对于每组数据输出一行,即内存置换上花费的时间。
Sample Input 1
3 4 5 1 2 3 4 18 2 1 2 3 1 2 1 2 2 3 2 3 1 1 2 3 2 1 4 6 1 1 2 3 4 5 6
Sample Output 1
4 11 6
Hint
样例1
因为内存一开始是空的,所以直接读入即可。
样例2

一开始移入11和22,在移入33的时候发现内存大小不足,所以按照先入先出顺序移出11。
直到下划线的第一个11时,发现此时内存里有11和22,所以不需要移入,直接读取即可。
所有下划线位置的数据不需要导入,因为内存里已经有了,以上共计为1111秒。
其中,被圈出的元素因为此时内存中只含有前面左边的33和11,所以被迫移入并移除33。
样例3
每次读入都需要换出,所以需要花费66
题解:队列的简单应用
//
// main.cpp
//
//
// Created by Edwin on 2018-12-23.
// Copyright © 2018 Edwin. All rights reserved.
//
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0×7ffffff
#define EPS 1e-8
#define maxn 1000000+10
#define PI acos(-1.0)
#define pb push_back
using namespace std;
int is[maxn];
int main()
{
ll test,n,m;
cin>>test;
while(test--)
{
int n,m;
cin>>n>>m;
memset(is,0,sizeof(is));
int ans=0;
queue<int> q;
while(n--)
{
int x;
cin>>x;
if(q.size()<m&&!is[x])
{
ans++;
q.push(x);
is[x]=1;
}
else if(!is[x])
{
ans++;
is[x]=1;
is[q.front()]=0;
q.pop();
q.push(x);
}
}
cout<<ans<<endl;
}
return 0;
}