题目解析

题意分析

题目描述了一个$DVD$图书馆的管理问题。我们需要处理一系列$DVD$请求，目标是在处理完所有请求后，使$DVD$的插入次数最少。具体规则如下： 有$k$个$DVD$驱动器，每个驱动器同一时间只能存放一张$DVD$。 当请求的$DVD$已经在某个驱动器中时，无需任何操作。 如果请求的$DVD$不在任何驱动器中： 如果有空闲的驱动器，直接将$DVD$插入。 如果没有空闲的驱动器，需要选择一个驱动器中的$DVD$替换为当前请求的$DVD$，此时插入次数加$1$。 我们需要提前知道整个请求序列，并按照顺序处理请求，目标是使总插入次数最小。

解题思路

这是一个典型的缓存替换问题，类似于操作系统中的页面置换算法。最优策略是贪心算法中的**最远将来使用（$Farthest in Future$）**策略，即在需要替换时，选择当前缓存中未来最晚被请求的$DVD$进行替换。

具体步骤如下： 初始化一个集合$S$表示当前驱动器中的$DVD$集合，初始为空。 遍历请求序列，对于每个请求$x_i$： 如果$x_i$已经在$S$中，直接跳过。 如果$x_i$不在$S$中： 如果$|S| < k$，将$x_i$插入$S$，插入次数加$1$。 如果$|S| = k$，需要选择一个$DVD$替换： 遍历$S$中的每个$DVD$，找到在后续请求中最晚出现（或不再出现）的那个$DVD$，将其替换为$x_i$，插入次数加$1$。 3. 最终输出总插入次数。

复杂度分析

• 对于每个测试用例，需要遍历$n$个请求。
• 对于每个需要替换的请求，需要检查$k$个驱动器中的$DVD$，并在剩余请求中查找其下一次出现的位置。
• 最坏情况下，每次替换需要$O(k \cdot n)$时间。
• 总复杂度为$O(m \cdot n^2 \cdot k)$，由于$k \leq 10$且$n \leq 100$，完全可接受。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;

const int inf = 0x7fffffff;
int n, m, ans, op[105], pos[1000005];
bool exist[1000005];
int drive[15], temp[15];
//n为DVD drives数量
//m为操作数

int find(int opr) {
    int res = -1, opaa;
    for(int i = 1; i <= n; i++) {
        if(pos[op[drive[i]]] < opr)
            temp[i] = inf;
        else {
            for(int j = opr + 1; j <= m; j++) {
                if(op[drive[i]] == op[j]) {
                    temp[i] = j;
                    break;
                }
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        if(res < temp[i]) {
            res = temp[i];
            opaa = i;
            if(res == inf)
                break;
        }
    }
    return opaa;
}

void solve(int opr, int k) { //opr为操作数， k为正在使用的DVD drives编号
    if(opr > m)
        return;
    if(k > n) {
        if(exist[op[opr]])
            solve(opr + 1, k);
        else {
            ans++;
            int opaa = find(opr);
            exist[op[drive[opaa]]] = false;
            exist[op[opr]] = true;
            drive[opaa] = opr;
            solve(opr + 1, k);
        }
    }
    else {
        if(exist[op[opr]])
            solve(opr + 1, k);
        else {
            exist[op[opr]] = true;
            ans++;
            drive[k] = opr;
            solve(opr + 1, k + 1);
        }
    }
}

int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        // 手动初始化 exist 数组
        for (int i = 0; i < 1000005; ++i) {
            exist[i] = false;
        }
        // 手动初始化 drive 数组
        for (int i = 0; i < 15; ++i) {
            drive[i] = 0;
        }
        // 手动初始化 temp 数组
        for (int i = 0; i < 15; ++i) {
            temp[i] = 0;
        }
        // 手动初始化 pos 数组
        for (int i = 0; i < 1000005; ++i) {
            pos[i] = 0;
        }
        // 手动初始化 op 数组
        for (int i = 0; i < 105; ++i) {
            op[i] = 0;
        }

        ans = 0;
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= m; i++) {
            scanf("%d", &op[i]);
            pos[op[i]] = max(pos[op[i]], i);
        }
        solve(1, 1);
        printf("%d\n", ans);
    }
    return 0;
}