牛客25380题解析：分层容器倒酒问题的C++解题策略与代码详解

ftggdnt

一、题目解读

牛客25380题要求处理一个分层容器倒酒模拟问题：给定N层容器的初始容量，以及M次操作（查询或倒酒），需动态更新容器状态并输出结果。题目核心在于理解倒酒时的容量限制与溢出处理逻辑，属于算法中的动态模拟类问题。

二、解题思路

本题采用“分层容量动态模拟”策略：

1. 用vector存储每层容量与当前水量，实现快速读写；

2. 通过循环处理操作：查询直接输出对应层状态，倒酒时需计算剩余容量，若溢出则逐层传递；

3. 关键优化：利用“当前水量”变量减少重复计算，避免超限判断错误。

三、解题步骤

1. 初始化：读入层数N、操作数M，构建容量数组并初始化当前水量为0；

2. 操作处理循环：

○ 若op=1，直接输出指定层当前水量；

○ 若op=2，执行倒酒操作：计算目标层剩余容量，若倒酒量≤剩余容量则直接更新，否则溢出至下一层递归处理；

3. 边界控制：通过x<n确保不越界，v递减至0时终止倒酒循环。

四、代码及注释

1. #include <iostream>
   
2. #include <vector>
   
3. using namespace std;
   
4. 
   
5. int main() {
   
6.     ios::sync_with_stdio(false);  // 关闭同步加速输入
   
7.     cin.tie(nullptr);
   
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层当前水量（注意索引转换）
    
26.         } else {                // 倒酒操作
    
27.             int x;
    
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. }

复制代码

五、总结

该解法通过分层状态维护与精确溢出计算，实现了高效模拟。关键在于利用局部变量优化容量判断，避免全局遍历。适用于处理具有层级依赖的动态资源分配问题，可拓展至类似“流量分配”场景。

转载：牛客25380题解析：分层容器倒酒问题的C++解题策略与代码详解