今日学习在线编程题：仙水购置

在线编程题：仙水购置"/>

今日学习在线编程题：仙水购置

题目来源：码蹄集

时间限制：1000ms
内存限制：65535kb

题目描述：W有N个瓶子，都是由十分珍贵的材料制作的，所以他一直只有N个，以至于当她需要多于N种的仙水时，不得不把某一种仙水倒掉来盛放最新需要的仙水。
现在W需要完成一项工作，需要使用瓶子的仙水，如果瓶子里缺少当前需要的仙水，她就会去购买，初始她的瓶子里没有任何一种仙水
现在给定一个W需要的长度为p的仙水序列，问W至少需要购买多少次仙水，
如果瓶子里没有W需要的仙水，她不得不倒掉某一种，但不清楚应该倒哪一种，你可以帮W决定倒哪一种，来使她购买仙水的次数最少。

输入格式：若干组数据
请读取到文件末尾
对于每组数据，第一行三个数，N，m（W用到的仙水种类数，用1到m来表示），p(表示序列长度）
第二行p个数，仙水序列
输出格式：对于每一组数据输出一行，一个数字，表示最少的购买次数。

输入样例：

2 3 5
3 1 2 1 2
3 4 5 
3 2 1 4 3
输出样例：

3
4

备注：

提示    
（0 < n,m,p <= 50000）
一种仙水可以反复使用的，只要在瓶子里，使用次数就无限

参考程序：

#include<bits/stdc++.h>using namespace std;
const int N=1e5+10;
int a[N], vis[N], ne[N], last[N];
priority_queue<pair<int,int>>l;
void init(){while(!l.empty()) l.pop();memset(vis,0,sizeof(vis));memset(ne,0,sizeof(ne));memset(last,1000010,sizeof(last));
}
int main()
{   int n,m,q;while(cin >> n >> m >> q){init();for(int i=1;i<=q;i++)cin>>a[i];for(int i=q;i>=1;i--){ne[i]=last[a[i]];last[a[i]]=i;}int ans=0;for(int i=1;i<=q;i++){if(ans<n&&!vis[a[i]]){ans++;vis[a[i]]=1;}else if(ans>=n&&!vis[a[i]]){ans++;vis[l.top().second]=0;vis[a[i]]=1;l.pop();}l.push({ne[i],a[i]});}cout<<ans<<endl;}return 0;
}