2016년 5월 10일 화요일

1700 - 멀티탭 스케줄링

https://www.acmicpc.net/problem/1700

멀티탭에 k개 이상 꽂아야하는 순간 하나를 뽑는다. 뽑아야할 녀석은 가장 나중에 사용되는 플러그부터 뽑는다. 그런게 없다면 아무거나 뽑는다.


#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, k;
    scanf("%d %d", &k, &n);
    vector<int> v(n);
    for(int i=0; i<n; ++i) scanf("%d", &v[i]);
    
    int ret = 0, idx = 0;
    vector<bool> pluged(101, false);
    int curK = 0, lastPush = v.front();
    for(int i=0; i<n; ++i){
        if(pluged[v[i]]) continue;
        curK += 1;
        if(curK > k){
            vector<int> lastUse(101, n);
            int cand = -1, maxD = -1;
            for(int j=0; j<i; ++j){
                if(!pluged[v[j]]) continue;
                for(int k=i+1; k<n; ++k){
                    if(v[j] == v[k]){
                        lastUse[v[j]] = k;
                        break;
                    }
                }
                if(maxD < lastUse[v[j]]){
                    maxD = lastUse[v[j]];
                    cand = v[j];
                }
            }
            if(cand == -1) cand = lastPush;
            //printf("push:%d, then pop: %d\n", v[i], cand);
            ret += 1;
            pluged[cand] = false;
        }
        lastPush = v[i];
        pluged[v[i]] = true;
    }
    printf("%d", ret);
    return 0;
}
댓글 쓰기

게시글 목록