【题目来源】
学而思编程：浇水
【题目描述】
皮皮和小美打算给花园里的 \(n\) 株植物浇水。
植物排成一行，编号从左到右依次从 \(1\) 到 \(n\)。其中，第 \(i(1≤i≤n)\) 株植物的位置 \(x=i\)，需要浇的水量为 \(w_i\) 升。皮皮和小美每人有一个水罐，其中皮皮的水罐容量为 \(A\) 升，小美的水罐的容量为 \(B\) 升，初始时，两个水罐都装满了水。
皮皮从左到右给植物浇水，从第 \(1\) 株植物开始。小美从右到左给植物浇水，从第 \(n\) 株植物开始。他们俩同时开始给植物浇水。
皮皮和小美各自为每株植物浇水时，每分钟浇 \(1\) 升水，也就是每过去一分钟，水罐中的水减少 \(1\) 升，植物还需要浇的水也减少 \(1\) 升。如果当前植物所需浇水量减为 \(0\)，就移动到下一棵植物（对于皮皮是编号大 \(1\) 的植物，对于小美是编号小 \(1\) 的植物），移动的时间忽略不计。
如果浇水途中水罐中的水耗尽了，一个超强水泵会用 \(T\) 分钟的时间，重新灌满水罐，然后重新开始浇水。
如果某人到达一株植物时，另一个人已经先到了，那么就只让先到的人浇水。如果皮皮和小美同时到达，就让皮皮完成浇水。
请你实现一个程序，求为所有植物完成浇水的时间。
【输入】
第 \(1\) 行包含 \(4\) 个正整数 \(n,A,B,T\)。
第 \(2\) 行，\(n\) 个正整数 \(w_1,w_2,…,w_n\)。
【输出】
输出一行，一个整数，表示答案。
【输入样例】
5 1 9 5
7 3 2 3 2
【输出样例】
37
【核心思想】
-
问题分析：给定 \(n\) 株植物排成一行，每株需水量 \(w_i\)。皮皮从左到右（\(1 \to n\)）、小美从右到左（\(n \to 1\)）同时浇水，每人水罐容量分别为 \(A\) 和 \(B\)，浇水速度 \(1\) 升/分钟，水耗尽后需 \(T\) 分钟重新灌满。若两人到达同一株植物，先到者浇（同时到则皮皮浇）。求全部浇完的总时间。这是一个双指针模拟问题，核心在于两人独立推进，用双指针追踪各自进度，总时间取两者最大值。
-
算法选择：
- 双指针：\(l\) 从 \(1\) 向右，\(r\) 从 \(n\) 向左，分别代表皮皮和小美当前处理的植物
- 贪心调度：每次选择当前总时间较小的一方先处理下一株植物（确保先到者先浇）
-
关键步骤：
- 初始化：读取 \(n, A, B, T\)、需水量数组 \(w[1..n]\)
- 辅助函数 \(water(x, X, w)\)：
- 计算当前剩余水量 \(x\) 浇灌需水量 \(w\) 所需的加水次数：\(cnt = \lceil (w - x) / X \rceil\)
- 更新剩余水量：\(x = x + cnt \times X - w\)
- 返回所需时间：\(w + cnt \times T\)（浇水时间 \(w\) + 加水时间 \(cnt \times T\)）
- 双指针模拟（\(l = 1, r = n, tl = 0, tr = 0, wl = A, wr = B\)）：
- 当 \(tl \leq tr\)：皮皮先处理植物 \(l\)，\(tl += water(wl, A, w[l++])\)
- 否则：小美先处理植物 \(r\)，\(tr += water(wr, B, w[r--])\)
- 输出答案：\(\max(tl, tr)\)
-
时间/空间复杂度：
- 时间复杂度：\(O(n)\)，每株植物被处理一次
- 空间复杂度：\(O(n)\)，存储需水量数组
-
双指针的核心思想：
- 相向推进：皮皮和小美从两端向中间靠拢，用 \(l\) 和 \(r\) 指针分别追踪
- 贪心选择：每次让当前总时间较小的一方先行动，确保"先到先浇"的规则被满足，同时最小化总完成时间（类似流水线调度）
- 加水次数计算：向上取整 \(\lceil (w - x) / X \rceil\) 确保水量足够浇灌当前植物，剩余水量留给下一株
- 时间累积：各自独立累积时间，最终答案取两者最大值（最后完成的一方决定总时间）
- 适用于双向并行处理、资源约束调度、相向双指针类问题
【算法标签】
双指针
【代码详解】
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 100005;
int n, A, B, T; // n: 货物数量，A: 左机器人加水速度，B: 右机器人加水速度，T: 移动单位时间
int w[N]; // 货物重量数组
int water(int &x, int X, int w) // 计算加水时间函数
{int cnt = ceil(1.0*(w-x)/X); // 计算需要加水的次数x = x + cnt * X - w; // 更新剩余水量return w + cnt * T; // 返回所需时间
}
signed main()
{cin >> n >> A >> B >> T; // 输入参数for (int i=1; i<=n; i++) // 输入货物重量cin >> w[i];int l = 1, r = n, tl = 0, tr = 0, wl = A, wr = B; // 初始化指针和时间while (l<=r) // 双指针处理{if (tl <= tr) // 如果左机器人总时间小于等于右机器人tl += water(wl, A, w[l++]); // 左机器人处理货物else // 否则tr += water(wr, B, w[r--]); // 右机器人处理货物}cout << max(tl, tr) << endl; // 输出最大时间return 0;
}
【运行结果】
5 1 9 5
7 3 2 3 2
37