Ice Cream Machines 题解

问题分析

这是一个经典的最优缓存置换问题。我们需要将$k$台冰淇淋机视为缓存，顾客的口味请求序列视为访问序列，机器清洗操作对应缓存未命中。

核心算法：Belady最优算法

Belady算法在离线情况下（已知完整请求序列）是最优的。策略是：当需要替换时，选择最远将来再次使用的口味进行替换。

数据结构设计

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N 200005

typedef struct {
    int flavor;        // 口味编号
    int next_use;      // 下一次使用时间
    int in_machine;    // 是否在机器中
} MachineState;

typedef struct {
    int flavor;
    int next_use;
} HeapNode;

完整代码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAX_N 200005
#define MAX_M 200005

// 顾客请求序列
int customers[MAX_N];
// 每个位置的下一次使用时间
int next_use[MAX_N];
// 每种口味最后出现的位置
int last_pos[MAX_M];
// 记录口味当前在哪个机器中 (-1表示不在)
int flavor_in_machine[MAX_M];

// 机器状态堆（最大堆，按next_use排序）
typedef struct {
    int flavor;
    int next_use;
} HeapNode;

HeapNode machine_heap[MAX_N];
int heap_size = 0;

// 堆操作函数
void swap(HeapNode *a, HeapNode *b) {
    HeapNode temp = *a;
    *a = *b;
    *b = temp;
}

void heap_push(int flavor, int next_use) {
    int i = heap_size++;
    machine_heap[i].flavor = flavor;
    machine_heap[i].next_use = next_use;
    
    // 上浮
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (machine_heap[parent].next_use >= machine_heap[i].next_use) break;
        swap(&machine_heap[parent], &machine_heap[i]);
        i = parent;
    }
}

HeapNode heap_pop() {
    HeapNode result = machine_heap[0];
    machine_heap[0] = machine_heap[--heap_size];
    
    // 下沉
    int i = 0;
    while (1) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;
        
        if (left < heap_size && machine_heap[left].next_use > machine_heap[largest].next_use)
            largest = left;
        if (right < heap_size && machine_heap[right].next_use > machine_heap[largest].next_use)
            largest = right;
            
        if (largest == i) break;
        swap(&machine_heap[i], &machine_heap[largest]);
        i = largest;
    }
    
    return result;
}

// 从堆中移除指定口味
void heap_remove(int flavor) {
    int i;
    for (i = 0; i < heap_size; i++) {
        if (machine_heap[i].flavor == flavor) break;
    }
    if (i == heap_size) return;
    
    machine_heap[i] = machine_heap[--heap_size];
    
    // 调整堆
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (machine_heap[parent].next_use >= machine_heap[i].next_use) break;
        swap(&machine_heap[parent], &machine_heap[i]);
        i = parent;
    }
    
    // 下沉
    while (1) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;
        
        if (left < heap_size && machine_heap[left].next_use > machine_heap[largest].next_use)
            largest = left;
        if (right < heap_size && machine_heap[right].next_use > machine_heap[largest].next_use)
            largest = right;
            
        if (largest == i) break;
        swap(&machine_heap[i], &machine_heap[largest]);
        i = largest;
    }
}

int main() {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    
    // 读取顾客请求
    for (int i = 0; i < n; i++) {
        scanf("%d", &customers[i]);
    }
    
    // 初始化
    memset(last_pos, -1, sizeof(last_pos));
    memset(flavor_in_machine, -1, sizeof(flavor_in_machine));
    
    // 预处理每个位置的下一次使用时间
    for (int i = n - 1; i >= 0; i--) {
        int flavor = customers[i];
        if (last_pos[flavor] != -1) {
            next_use[i] = last_pos[flavor];
        } else {
            next_use[i] = n;  // 设置为n表示不会再使用
        }
        last_pos[flavor] = i;
    }
    
    int washes = 0;
    int machines_used = 0;
    
    // 处理每个顾客请求
    for (int i = 0; i < n; i++) {
        int current_flavor = customers[i];
        
        // 如果口味已经在机器中
        if (flavor_in_machine[current_flavor] != -1) {
            // 从堆中移除旧记录
            heap_remove(current_flavor);
            // 添加新记录
            heap_push(current_flavor, next_use[i]);
            flavor_in_machine[current_flavor] = i;
            continue;
        }
        
        // 需要清洗机器
        washes++;
        
        // 如果有空机器
        if (machines_used < k) {
            heap_push(current_flavor, next_use[i]);
            flavor_in_machine[current_flavor] = i;
            machines_used++;
        } else {
            // 替换最远将来使用的口味
            HeapNode to_remove = heap_pop();
            flavor_in_machine[to_remove.flavor] = -1;
            
            // 添加新口味
            heap_push(current_flavor, next_use[i]);
            flavor_in_machine[current_flavor] = i;
        }
    }
    
    printf("%d\n", washes);
    return 0;
}

算法步骤详解

1. 预处理阶段

// 计算每个位置的下一次使用时间
for (int i = n - 1; i >= 0; i--) {
    int flavor = customers[i];
    if (last_pos[flavor] != -1) {
        next_use[i] = last_pos[flavor];
    } else {
        next_use[i] = n;  // 不会再使用
    }
    last_pos[flavor] = i;
}

2. 主处理循环

for (int i = 0; i < n; i++) {
    // 检查是否已在机器中
    if (flavor_in_machine[current_flavor] != -1) {
        // 更新使用时间
        continue;
    }
    
    // 需要清洗
    washes++;
    
    if (machines_used < k) {
        // 使用空机器
        machines_used++;
    } else {
        // 替换最远将来使用的机器
        HeapNode to_remove = heap_pop();
        flavor_in_machine[to_remove.flavor] = -1;
    }
    
    // 添加新机器状态
    heap_push(current_flavor, next_use[i]);
    flavor_in_machine[current_flavor] = i;
}

复杂度分析

• 时间复杂度：$O(n \log k)$
  • 预处理：$O(n)$
  • 主循环：每个顾客$O(\log k)$的堆操作
• 空间复杂度：$O(n + m)$
  • 存储请求序列和状态信息

关键优化点

1. 高效的下一次使用时间计算：从后往前遍历，$O(n)$完成
2. 最大堆维护机器状态：快速找到最远将来使用的机器
3. 快速查找机制：通过flavor_in_machine数组$O(1)$判断口味是否在机器中

测试样例验证

样例1：$k = 1$

输入: 8 3 1
序列: 2,3,3,1,2,1,1,3
输出: 6

样例2：$k = 2$

输入: 8 3 2  
序列: 2,3,3,1,2,1,1,3
输出: 4

注意事项

1. 数组大小：根据数据范围设置足够的数组大小
2. 初始化：确保所有数组正确初始化
3. 堆维护：实现正确的堆操作函数
4. 边界情况：处理不会再出现的口味（设置为$n$）

这个C语言实现完全遵循Belady最优算法，能够在题目要求的数据范围内高效运行。