【題目敘述】 https://zerojudge.tw/ShowProblem?problemid=a068
【解題想法】Greedy
- episode[i]：(array) 第 i 集動畫存放的硬碟編號
- HDD[i]：(vector) 存放在 HDD-i 的所有動畫
- st：set<使用該硬碟的下一集動畫, 連上USB的硬碟編號>
- connected：set<目前連上USB的所有硬碟>
- 依序檢查每一集動畫(i)及其使用的硬碟(cur_HDD = episode[i])：
- 如果USB未用滿，且該硬碟未曾連結, 將該硬碟及其下一集加入st。
- 如果USB未用滿，但該硬碟已連結, 更新該硬碟的下一集。
- 如果USB已用滿，且該硬碟已連結, 更新該硬碟的下一集。
- 如果USB已用滿，且該硬碟未曾連結, 取代st中下一集最遠的硬碟。同時更新connected，cnt++。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>
#include <utility>
using namespace std;
vector<int> HDD[100005]; // 每顆HDD出現的集數
int episode[1000005]; // 儲存該集的硬碟#
int nxt[100005]; // 每顆HDD下一集要播放的集數
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int TC, N, M;
int cur_HDD, nxt_episode;
pair<int,int> to_swap;
cin >> TC;
while (TC--){
memset(episode, 0, sizeof(episode));
memset(nxt, 0, sizeof(nxt));
cin >> N >> M;
for(int i = 0 ; i <= 100005 ; i++){
HDD[i].clear();
}
for (int i = 1; i <= N; i++){
cin >> episode[i];
HDD[episode[i]].push_back(i);
}
for (int i = 0; i < 100005; i++)
HDD[i].push_back(1e9); // no more episodes in this HDD
int cnt = 0;
set<pair<int,int> > st;
set<int> connected;
for (int i = 1; i <= N; i++){
cur_HDD = episode[i];
if (st.size() < M) {
if (connected.count(cur_HDD))
st.erase({i, cur_HDD});
else
connected.insert(cur_HDD);
} else if (connected.count(cur_HDD)) {
st.erase({i, cur_HDD});
} else {
to_swap = *(--st.end());
connected.erase(to_swap.second);
st.erase(to_swap);
cnt++;
connected.insert(cur_HDD);
}
nxt_episode = *upper_bound(HDD[cur_HDD].begin(), HDD[cur_HDD].end(), i);
st.insert({nxt_episode, cur_HDD});
}
cout << cnt << "\n";
}
}