经典面替换算法,每次选择最远的那个碟片请求进行替换。
AC代码
#include <cstdio> #include <cmath> #include <algorithm> #include <cstring> #include <utility> #include <string> #include <iostream> #include <map> #include <set> #include <vector> #include <queue> #include <stack> using namespace std; #pragma comment(linker, "/STACK:1024000000,1024000000") #define eps 1e-10 #define inf 0x3f3f3f3f #define PI pair<int, int> typedef long long LL; const int maxn = 10000 + 5; queue<int>pos[maxn]; int a[105], driv[15]; int k, n; int solve() { int ans = 0, cnt = 0; for(int i = 0; i < n; ++i) { int ok = 0; for(int j = 0; j < cnt; ++j) { if(driv[j] == a[i]) { ok = 1; break; } } if(!ok) { ++ans; if(cnt < k) { driv[cnt++] = a[i]; } else if(cnt == k) { int ind = 0, far = -1; for(int j = 0; j < k; ++j) { int p = pos[driv[j]].empty() ? inf : pos[driv[j]].front(); if(p > far) { ind = j; far = p; } } driv[ind] = a[i]; } } pos[a[i]].pop(); } return ans; } int main() { int T; scanf("%d", &T); while(T--) { scanf("%d%d", &k, &n); for(int i = 0; i < n; ++i) { scanf("%d", &a[i]); pos[a[i]].push(i); } printf("%d\n", solve()); } return 0; }
如有不当之处欢迎指出!