1528: [POI2005]sam-Toy Cars

Description

Jasio 是一個三歲的小男孩,他最喜歡玩玩具了,他有n 個不同的玩具,它們都被放在了很高的架子上所以Jasio 拿不到它們. 為了讓他的房間有足夠的空間,在任何時刻地板上都不會有超過k 個玩具. Jasio 在地板上玩玩具. Jasio'的媽媽則在房間里陪他的兒子. 當Jasio 想玩地板上的其他玩具時,他會自己去拿,如果他想玩的玩具在架子上,他的媽媽則會幫他去拿,當她拿玩具的時候,順便也會將一個地板上的玩具放上架子使得地板上有足夠的空間. 他的媽媽很清楚自己的孩子所以他能夠預料到Jasio 想玩些什么玩具. 所以她想盡量的使自己去架子上拿玩具的次數盡量的少,應該怎么安排放玩具的順序呢?

Input

第一行三個整數: n, k, p (1 <= k <= n <= 100.000, 1 <= p <= 500.000), 分別表示玩具的總數,地板上玩具的最多個數以及Jasio 他想玩玩具的序列的個數,接下來p行每行描述一個玩具編號表示Jasio 想玩的玩具.

Output

一個數表示Jasio 的媽媽最少要拿多少次玩具.

Sample Input

3 2 7
1
2
3
1
3
1
2

Sample Output

4

HINT

Source

?

?

【分析】

　　貪心很可以。記錄下每個玩具下次出現的位置，每次要刪的話選一個最遠的刪掉。用優先隊列優化。

?

1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 #include<cmath> 7 #include<queue> 8 #include<vector> 9 using namespace std; 10 #define Maxn 500010 11 12 int a[Maxn],first[Maxn],nt[Maxn]; 13 bool mark[Maxn]; 14 15 struct node 16 { 17 int x,y; 18 friend bool operator < (node x,node y) 19 { 20 return x.x<y.x; 21 } 22 }; 23 24 priority_queue<node > q; 25 26 int main() 27 { 28 int n,k,p; 29 scanf("%d%d%d",&n,&k,&p); 30 for(int i=1;i<=p;i++) scanf("%d",&a[i]); 31 memset(first,0,sizeof(first)); 32 for(int i=p;i>=1;i--) 33 { 34 nt[i]=first[a[i]]; 35 first[a[i]]=i; 36 } 37 for(int i=1;i<=p;i++) if(nt[i]==0) nt[i]=p+1; 38 memset(mark,0,sizeof(mark)); 39 int cnt=0,ans=0; 40 while(!q.empty()) q.pop(); 41 for(int i=1;i<=p;i++) 42 { 43 if(!mark[a[i]]) 44 { 45 ans++; 46 if(cnt<k) cnt++; 47 else 48 { 49 node nw=q.top();q.pop(); 50 mark[nw.y]=0; 51 } 52 mark[a[i]]=1; 53 } 54 node now; 55 now.x=nt[i];now.y=a[i]; 56 q.push(now); 57 } 58 printf("%d\n",ans); 59 return 0; 60 } View Code

?

2017-01-13?21:20:41

轉載于:https://www.cnblogs.com/Konjakmoyu/p/6284150.html

總結

以上是生活随笔為你收集整理的【BZOJ 1528】 1528: [POI2005]sam-Toy Cars （贪心+堆）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。