题意分析

1. 问题背景

   • 一家高级货物运输有限公司有一个大型仓库，存储多种货物。
   • 仓库有 $B$ 个货位（$1 \leq B \leq 1000$）。
   • 货物类型有 $G$ 种（$1 \leq G \leq 1,000,000$）。
   • 每天有 $N$ 辆卡车（$1 \leq N \leq 1,000,000$）来装载货物，每辆卡车仅装载一种类型。

2. 操作规则

   • 管理员提前将货物搬运到货位，但无法预知每辆卡车的具体需求，因此会准备比实际需求更多的货物。
   • 如果当前卡车装载的货物类型与前一辆相同，则无需重新搬运货物（节省操作）。
   • 每个货位可以服务任意数量的卡车，只要货物类型相同。
   • 目标：最小化“LOAD”操作次数（即搬运货物到货位的次数）。

3. 输入格式

   • 第一行：测试用例数量 $T$。
   • 每个测试用例：
     • 第一行：$B$（货位数）、$G$（货物类型数）、$N$（卡车数）。
     • 接下来 $N$ 行：每行一个整数 $t_i$（第 $i$ 辆卡车的货物类型）。

4. 输出格式

   • 每个测试用例：
     • 第一行：Case X:（$X$ 为测试用例编号）。
     • 接下来 $N$ 行：
       • NO ACTION（当前货物已在货位上）。
       • LOAD b g（将货物 $g$ 搬运到货位 $b$）。
   • 不同测试用例之间用空行分隔。

解题思路

1. 数据结构

   • 使用数组 bay[B] 记录每个货位存放的货物类型（初始化为 $-1$）。

2. 处理每辆卡车

   • 对于卡车 $i$ 的货物 $t_i$：
     • 检查是否已有货位存放 $t_i$：
       • 如果有，输出 NO ACTION。
     • 否则：
       • 优先使用空货位（bay[j] == -1）。
       • 若无空货位，则替换一个已有货物的货位（如第一个货位）。
       • 输出 LOAD b t_i（$b$ 为货位编号）。

标程（C++）