模拟算法实战：牛客25380题分层倒酒问题的优雅解法

ftggdnt

一、问题背景与理解

牛客25380题描述了一个有趣的分层倒酒问题：有n层容器，每层有固定容量。我们需要处理两种操作：查询某层的当前酒量，以及从指定层开始倒入一定量的酒（当一层装满后，多余酒量会自动流向下一层）。这是一个典型的模拟类问题，考验对实际问题抽象建模和流程控制的能力。

二、完整代码实现（带详细注释）

1. #include <iostream>
   
2. #include <vector>
   
3. using namespACe std;
   
4. 
   
5. int main() {
   
6.     ios::sync_with_stdio(false);  // 禁用C与C++的输入输出同步，提升IO速度
   
7.     cin.tie(nullptr);            // 解除cin与cout的绑定，进一步提速
   
8.    
   
9.     int n, m;                   // n-层数，m-操作次数
   
10.     cin >> n >> m;
    
11.     vector<long long> capacity(n);  // 每层的**容量
    
12.     vector<long long> current(n, 0); // 每层当前酒量，初始为0
    
13.    
    
14.     // 读取每层初始容量
    
15.     for (int i = 0; i < n; ++i) {
    
16.         cin >> capacity[i];
    
17.     }
    
18.    
    
19.     while (m--) {               // 处理m个操作
    
20.         int op;
    
21.         cin >> op;
    
22.         if (op == 1) {          // 查询操作
    
23.             int k;
    
24.             cin >> k;
    
25.             cout << current[k-1] << "\n";  // 输出第k层当前酒量(转换为0-based)
    
26.         } else {                // 倒酒操作
    
27.             int x;              // 起始层(1-based)
    
28.             long long v;        // 倒酒量
    
29.             cin >> x >> v;
    
30.             x--;                // 转换为0-based索引
    
31.             
    
32.             // 从指定层开始倒酒
    
33.             while (v > 0 && x < n) {  // 还有酒未倒完且还有下层
    
34.                 long long available = capacity[x] - current[x]; // 当前层剩余容量
    
35.                 if (v <= available) { // 当前层可以容纳全部剩余酒量
    
36.                     current[x] += v;
    
37.                     v = 0;            // 酒已倒完
    
38.                 } else {              // 当前层会被装满
    
39.                     current[x] = capacity[x]; // 装满当前层
    
40.                     v -= available;   // 减去已倒入的量
    
41.                     x++;              // 处理下一层
    
42.                 }
    
43.             }
    
44.         }
    
45.     }
    
46.    
    
47.     return 0;
    
48. }

复制代码

三、算法核心思想

• 模拟过程：忠实按照题目描述的物理过程进行模拟
• 状态维护：使用两个数组分别记录各层的容量和当前酒量
• 操作处理：区分查询和倒酒两种操作类型
• 溢出处理：自动将多余酒量流向下一层的逻辑实现
  
  

四、关键技巧分析

• IO优化：使用ios::sync_with_stdio(false)和cin.tie(nullptr)加速输入输出
• 索引处理：注意1-based和0-based索引的转换
• 循环控制：通过while(v > 0 && x < n)同时控制酒量和层数边界
• 剩余容量计算：capacity[x] - current[x]的巧妙运用
  
  

五、复杂度分析

• 时间复杂度：O(m × n) 最坏情况下每次倒酒操作需要遍历所有层
• 空间复杂度：O(n) 仅需存储各层容量和当前酒量
  
  

六、扩展思考

• 如何优化大量倒酒操作的情况？
• 如果酒可以向上流动（如负压情况），代码需要如何修改？
• 如何扩展支持删除酒的操作？
  
  

参考：学习资料