멀티탭 스케쥴링 2 (multitap2) (JUNGOL 1670)

https://jungol.co.kr/problem/1670

---

아이디어

새로운 전기제품을 꽂을 때 어떤 전기제품의 콘센트를 뺄지만 구해주면 됩니다.

꽂혀있는 N개의 전기제품중에서 바로 다음에 사용하는것이 가장 늦은 전기제품을 빼는것이 최적입니다.

---

소스코드

#include <iostream>
#include <set>
#define ll long long
using namespace std;

ll Num[303030]={0};
ll LastIdx[303030]={0};
ll arr[303030]={0};

bool Now[303030]={0};

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N,K,i;

    cin>>N>>K;
    for (i=1;i<=K;i++) cin>>arr[i];
    for (i=1;i<=K;i++) Num[i]=K+1;
    for (i=K;i>=1;i--)
    {
        LastIdx[i]=Num[arr[i]];
        Num[arr[i]]=i;
    }

    ll res=0;
    set <pair <ll,ll> > st;
    for (i=1;i<=K;i++)
    {
        if (Now[arr[i]])
        {
            st.erase({i,arr[i]});
            st.insert({LastIdx[i],arr[i]});
        }
        else if (st.size()<N)
        {
            st.insert({LastIdx[i],arr[i]});
            Now[arr[i]]=true;
        }
        else
        {
            auto [idx,type]=*st.rbegin();
            Now[type]=false;
            st.erase({idx,type});

            st.insert({LastIdx[i],arr[i]});
            Now[arr[i]]=true;

            res++;
        }
    }

    cout<<res;
}