bzoj 1206: [HNOI2005]虚拟内存

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <iostream>
 5 #include <queue>
 6 using namespace std;
 7 #define N 1000008
 8 
 9 struct page
10 {
11     int num,v,t;
12     bool operator <(const page &b) const
13         {if (v == b.v) return (t > b.t); return (v > b.v);}
14     page(int n1,int v1,int t1){num = n1; v = v1; t = t1;}
15 };
16 
17 int n,m,delta[N],ans,s[N],a[N],b[N];
18 bool at[N];
19 priority_queue<page> Q;
20 
21 bool cmp(int x,int y)
22 {
23     return (a[x] < a[y]);
24 }
25 
26 void init()
27 {
28     scanf("%d%d",&n,&m);
29     for (int i = 1;i <= m;i++) scanf("%d",&a[i]),s[i] = i;//输入 
30     sort(&s[1],&s[m+1],cmp);
31     for (int i = 1;i <= m;i++) 
32         b[s[i]] = (a[s[i]] == a[s[i-1]]?b[s[i-1]]:b[s[i-1]]+1);//离散化 
33 }
34 
35 int main()
36 {
37 //    freopen("input.txt","r",stdin);
38     
39     init();
40     for (int i = 1;i <= m;i++)
41     {
42         int k = b[i];
43         if (at[k]) delta[k]++,ans++;
44         else 
45         {
46             if (Q.size() == n)
47                 while (1)
48                 {
49                     page x = Q.top();
50                     Q.pop(); at[x.num] = false;
51                     if (!delta[x.num]) break ;
52                     x.v += delta[x.num],delta[x.num] = 0;
53                     if (Q.empty() || Q.top() < x) break ;
54                     Q.push(x); at[x.num] = true;
55                 }
56             Q.push(page(k,1,i)); at[k] = true;
57         }
58     }
59     printf("%d\n",ans);
60     return 0;
61 }