Time Lapse :25min 23sec

1700.c

c

#include <stdio.h>
#include <memory.h>
int use[100];
int mtap[100];
int holes, K, ans = 0;
void OPT() {
	int predict[101];
	int hole = 0;
	for (int i = 0; i < K; ++i) {
		int flag = 0;
		for (int j = 0; j < hole; ++j)
			if (mtap[j] == use[i]) { flag = 1; break; }
		if (flag) continue;
		if (hole < holes) {
			mtap[hole] = use[i];
			++hole;
		}
		else {
			memset(predict, 0, sizeof(int)*(K+1));
			for (int j = i; j < K; ++j) {
				if (predict[use[j]]==0) predict[use[j]] = j;
			}
			int umax = 0;
			for (int j = 0; j < hole; ++j) {
				if (!predict[mtap[j]]) { flag = j;	break;	}
				else if (umax < predict[mtap[j]]) {
						umax = predict[mtap[j]];
						flag = j;
					}
			}
			++ans;
			mtap[flag] = use[i];
		}
	}
}
int main() {
	scanf("%d %d", &holes, &K);
	for (int i = 0; i < K; ++i)
		scanf("%d", &use[i]);
	OPT();
	printf("%d", ans);
}

c++

#include <iostream>
#include <list>
#include <map>
#include <unordered_map>
#include <vector>
#include <unordered_set>

using namespace std;

vector<vector<int>> use(101, vector<int>());
vector<int> seq(101);
int N, K;

int solution() {
    if(N >= K) return 0;

    int res = 0, idx = 0;
    unordered_set<int> inUsing;

    while(inUsing.size() != N) inUsing.insert(seq[idx++]);
    for(; idx < K; idx++) {
        if(inUsing.count(seq[idx])) continue;

        int removeItem = -1;
        int removeTime = -1;

        for(auto useItem : inUsing) {
            auto it = lower_bound(use[useItem].begin(), use[useItem].end(), idx);
            if(it == use[useItem].end()) {
                removeItem = useItem; break;
            }

            if(removeTime < *it) {
                removeTime = *it;
                removeItem = useItem;
            }
        }

        inUsing.erase(removeItem);
        inUsing.insert(seq[idx]);
        res++;
    }

    return res;
}
int main() {
    int item;
    scanf("%d %d",&N, &K);
    for(int i = 0; i < K; i++) {
        scanf("%d", &seq[i]);
        use[seq[i]].push_back(i);
    }
    cout<<solution();
}