【題解】ZeroJudge a068: E.看動畫 加強版

題目敘述】 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";
    }
}
分享本文 Share with friends