Template Library Management
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 627 Accepted Submission(s): 189
Problem Description
As an experienced ACMer, you must have known the importance of "code template library". With the help of pre-printed code library, you can implement the complicated algorithms correctly and efficiently. However, the size of the library
is strictly limited during the contest. For example, you can only take at most 25 pages of printed codes in World Finals. So you must choose carefully which code template should be included.
Now your team is participating a programming contest whose rules are slightly different from ICPC. This contest consists of N problems, and you must solved them in order: Before you solve the (i+1)th problem, you must solve the ith problem
at first. And solving the ith problem requires a specified code template Ti.
You are allowed to hold M code templates only. At the beginning of the contest, your are holding templates numbered 1, 2, ..., M. During the contest, if the problem you are trying to solve requires code template Ti, and Ti is happened
at your hand (i.e, one of the M code templates you are holding is Ti), you can solve it immediately. On the other hand, if you are not holding Ti, you must call your friends who are outside the arena for help (yes, it is permitted, not
cheating). They can give you the code template you need. Because you are only allowed to hold M code templates, after solving current problem, you must choose to drop the code you get from your friends just now, or to keep it and drop one of the M templates
at your hand previously.
Given the problem sequence in the contest and the limitation M, you want finish all the problems with minimum number of calling your friends.
is strictly limited during the contest. For example, you can only take at most 25 pages of printed codes in World Finals. So you must choose carefully which code template should be included.
Now your team is participating a programming contest whose rules are slightly different from ICPC. This contest consists of N problems, and you must solved them in order: Before you solve the (i+1)th problem, you must solve the ith problem
at first. And solving the ith problem requires a specified code template Ti.
You are allowed to hold M code templates only. At the beginning of the contest, your are holding templates numbered 1, 2, ..., M. During the contest, if the problem you are trying to solve requires code template Ti, and Ti is happened
at your hand (i.e, one of the M code templates you are holding is Ti), you can solve it immediately. On the other hand, if you are not holding Ti, you must call your friends who are outside the arena for help (yes, it is permitted, not
cheating). They can give you the code template you need. Because you are only allowed to hold M code templates, after solving current problem, you must choose to drop the code you get from your friends just now, or to keep it and drop one of the M templates
at your hand previously.
Given the problem sequence in the contest and the limitation M, you want finish all the problems with minimum number of calling your friends.
Input
The first line of each test case contains two numbers N (1 <= N <= 100000) and M (1 <= M <= 100000). The second line contains N numbers T1, T2, ..., TN (1 <= Ti <= 109), indicating
the code templates required by each problem.
the code templates required by each problem.
Output
Output one line for each test case, indicating the minimum number of calling friends for help.
Sample Input
4 3 1 2 3 4 11 3 4 1 2 1 5 3 4 4 1 2 3
Sample Output
1 4
Author
RoBa
Source
思路：
贪心，如果要淘汰一个模板T，就要淘汰下一个T坐标最远的那个。预处理每一个T的下一个T的位置，然后用set操作就好了。
ps：
1.不知为什么，同为STL操作，我的代码要比别人慢的多，大神求解。
2.set在调用insert时才排序，如果单单改变元素比较函数的值，是不会帮你重新排序的，如果没有重新排序，那么进行其他操作时就会出错，这也是为什么要用两个set的原因。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#pragma comment (linker,"/STACK:102400000,102400000")
#define maxn 100005
#define MAXN 300005
#define mod 1000000007
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-6
typedef long long ll;
using namespace std;
int n,m,ans,cnt;
int a[maxn],pp[maxn];
map<int,int>next;
struct Node
{
int u;
bool operator < (const Node &xx)const
{
return next[u]>next[xx.u];
}
}cur;
multiset<Node>s;
set<int>mys;
void solve()
{
int i,j,t;
ans=0;
s.clear();
mys.clear();
for(i=1; i<=m; i++)
{
if(!next[i]) next[i]=n+1;
cur.u=i;
mys.insert(i);
s.insert(cur);
}
for(i=1; i<=n; i++)
{
t=next[a[i]];
cur.u=a[i];
if(mys.find(a[i])!=mys.end()) // 有的话更新
{
s.erase(cur); // 这里需要删除了再插入 不然不会帮你排序的
next[a[i]]=pp[t];
s.insert(cur); // 不要以为pp[t]=n+1就不要插了
}
else // 没有的话维护set
{
ans++;
next[a[i]]=pp[t];
if(pp[t]>=next[(*s.begin()).u]) continue ; // 小剪枝
mys.insert(a[i]);
s.insert(cur);
mys.erase((*s.begin()).u); // 每次删除next[]最大的
s.erase(s.begin());
}
}
}
int main()
{
int i,j,t;
while(~scanf("%d%d",&n,&m))
{
for(i=1; i<=n; i++)
{
scanf("%d",&a[i]);
}
next.clear();
for(i=n; i>=1; i--)
{
if(next[a[i]]) t=next[a[i]];
else t=n+1;
next[a[i]]=i;
pp[i]=t;
}
pp[n+1]=n+1;
solve();
printf("%d\n",ans);
}
return 0;
}
/*
6 3
1000 99 86 86 87 99
20 3
1000 99 86 86 87 99 1000 68 86 8 8 8 9 6 8 99 98 97 1000 1000
ans:4 10
*/