首页P1223 排队接水C++

P1223 排队接水C++

时间: 2025-04-06 14:10:48 浏览: 84

### C++ 实现排队接水算法 P1223 #### 贪心算法的核心思想该问题可以通过贪心算法解决，其核心在于优先安排接水时间较短的人先完成接水操作。通过这种方式，能够使得总等待时间达到最小化[^1]。 #### 完整代码实现以下是基于上述思路的完整 C++ 代码： ```cpp #include <bits/stdc++.h> using namespace std; struct Person { int index; int time; }; bool compare(const Person& p1, const Person& p2) { return p1.time < p2.time; // 按照接水时间升序排列 } int main() { int n; cin >> n; vector<Person> people(n + 1); for (int i = 1; i <= n; ++i) { cin >> people[i].time; people[i].index = i; // 记录原始顺序 } sort(people.begin() + 1, people.end(), compare); double totalWaitTime = 0; int cumulativeTime = 0; for (int i = 1; i <= n; ++i) { if (i != 1) cout << " "; cout << people[i].index; // 输出调整后的顺序 cumulativeTime += people[i].time; // 当前累计时间 totalWaitTime += cumulativeTime - people[i].time; // 总等待时间累加 } cout << endl; cout << fixed << setprecision(2) << totalWaitTime / n; // 平均等待时间 return 0; } ``` #### 代码解析 1. **数据结构设计** 使用 `Person` 结构体存储每个人的编号 (`index`) 和接水所需的时间 (`time`)，以便后续处理时保留原始输入次序的信息[^3]。 2. **排序逻辑** 对所有人按照接水时间从小到大进行排序，从而满足贪心策略的要求[^4]。 3. **计算平均等待时间** 遍历已排序数组，在每次迭代中更新累积时间和总的等待时间，并最终输出平均值[^2]。 --- ###

阅读全文