题意分析

该题模拟图书管理员从储藏室取书并复印的全过程，学生排队请求书，并将书存放在若干桌子或书架上。目标是根据书的查找、取出、放回流程，计算所有请求的访问开销之和，其中对 $D_i$ 的访问开销为 $i$，对书架的访问开销为 $m+1$。

解题思路

• 使用一个队列模拟学生请求队列，每次处理队首学生的一个请求，处理完若学生还有后续请求，则重新入队。
• 使用 $m$ 个双端队列 $q[1..m] 模拟$D_1…D_m$，一个映射$id[book]$ 记录每本书当前所在位置（$1…m$ 或 $m+1$ 为书架）。初始所有书均在书架，$id[b]=m+1$。
• 取书：若 $id[b]=i\le m$，从 $q[i]$ 中删除；否则为 $m+1$。开销为当前位置 $i$ 或 $m+1$。
• 放书到 $D\_1$：尝试从 $D\_1$ 开始依次找第一个未满桌子（包括 $D\_1$），若都有满则放书架，更新 $id[b]$，开销为该位置索引。
• 若书放回 $D\_1$ 时 $D\_1$ 已满，则按题意顺序临时存放到LRU ，并淘汰 $D\_1$ 上最久未请求书 $t$→将 $t$ 放到下一个位置→取回请求书→放入 $D\_1$，中间每次放/取均累加相应开销。
• LRU 策略可通过 $q[1]$ 的队首表示最久未使用，队尾为最近使用。每次对 $D\_1$ 的访问后，将对应书移动到队尾以更新使用时间。

本题代码

#include <iostream>
#include <cstdio>
#include <deque>
#include <vector>
using namespace std;

int m, c, n;
deque<int> studentQ;            // 学生队列，存储有未完成请求的学生编号
deque<int> desk[11];            // desk[1..m] 模拟 D1..Dm
vector<int> requests[105];      // requests[i] 存储第 i 个学生的请求序列
int locationOf[105];            // locationOf[book]：1..m 表示在对应桌子，m+1 表示在书架

// 读取数据并初始化
bool readInput() {
    if (!(cin >> m >> c >> n) || (m==0 && c==0 && n==0)) return false;
    studentQ.clear();
    for (int i = 1; i <= n; i++) {
        int k; cin >> k;
        requests[i].clear();
        while (k--) {
            int b; cin >> b;
            requests[i].push_back(b);
        }
        if (!requests[i].empty()) studentQ.push_back(i);
    }
    for (int i = 1; i <= m; i++) desk[i].clear();
    for (int b = 1; b <= 100; b++) locationOf[b] = m+1;  // 初始都在书架
    return true;
}

// 将书放到从 from 桌子开始的第一个未满桌子，或书架
int putBook(int book, int from) {
    for (int i = from; i <= m; i++) {
        if ((int)desk[i].size() < c) {
            desk[i].push_back(book);
            locationOf[book] = i;
            return i;
        }
    }
    locationOf[book] = m+1;
    return m+1;
}

// 从当前位置取出书
int takeBook(int book) {
    int loc = locationOf[book];
    if (loc <= m) {
        // 从 desk[loc] 中删除
        for (auto it = desk[loc].begin(); it != desk[loc].end(); ++it) {
            if (*it == book) { desk[loc].erase(it); break; }
        }
    }
    return loc;
}

int main() {
    while (readInput()) {
        long long totalCost = 0;
        while (!studentQ.empty()) {
            int stu = studentQ.front(); studentQ.pop_front();
            int book = requests[stu].back();
            requests[stu].pop_back();
            if (!requests[stu].empty()) studentQ.push_back(stu);

            // 取书
            totalCost += takeBook(book);

            // 放到 D1
            int loc = putBook(book, 1);
            totalCost += loc;

            // 如果没放到 D1，需要进行 LRU 调整
            if (locationOf[book] != 1) {
                // 临时取出 D1 队首（最久未使用）
                int lruBook = desk[1].front();
                desk[1].pop_front();
                totalCost += 1;  // 取出开销 D1

                // 放到下一位置
                int loc2 = putBook(lruBook, 2);
                totalCost += loc2;

                // 取回请求书
                totalCost += takeBook(book);
                // 放回 D1
                totalCost += putBook(book, 1);
            }
        }
        cout << totalCost << "\n";
    }
    return 0;
}