贪心算法排队接水问题

### 排队接水问题的 Python 实现 排队接水问题是经典的贪心算法应用之一，其核心在于找到一种最优策略来最小化所有人等待时间的总和。以下是基于此问题的一个通用解决方案。 #### 1. 贪心算法的核心思路 为了使总的等待时间最少，应优先让所需接水时间较短的人先完成接水操作[^1]。这是因为越早结束接水的人会减少后续人员的整体等待时间。 #### 2. 示例代码实现 下面是一个完整的 Python 示例代码： ```python def min_waiting_time(n, times): """ 计算最小化的总等待时间。 参数: n (int): 队伍人数 times (list): 每个人所需的接水时间列表 返回: int: 总等待时间 """ # 对接水时间进行从小到大排序 times.sort() total_wait = 0 # 计算每个人的累计等待时间 for i in range(n): remaining_people = n - (i + 1) total_wait += times[i] * remaining_people return total_wait # 输入处理部分 if __name__ == "__main__": n = int(input("请输入队伍人数：")) times = list(map(int, input(f"请输入{n}人的接水时间（以空格分隔）：").split())) result = min_waiting_time(n, times) print(f"最小化的总等待时间为：{result}") ``` 上述代码实现了如下功能： - **输入**: 用户需提供队伍人数 `n` 和每个人对应的接水时间数组 `times`。 - **逻辑**: 将接水时间按升序排列后计算每一轮剩余人数的累积等待时间[^2]。 - **输出**: 输出最终的最小化总等待时间。 #### 3. 复杂度分析 该方法的时间复杂度主要由排序决定，即 \(O(N \log N)\)，其中 \(N\) 是队伍长度。由于每次只需遍历一次已排序数组即可得出结果，因此整体效率较高[^3]。 --- ####

### 贪心算法经典例题 Top 10 以下是基于贪心算法的经典例题总结，涵盖了多种应用场景： #### 1. 找零问题 描述：给定若干种面额的钱币数量，求最少钱币数目完成找零。 核心思想：尽可能多地使用大面额货币减少总张数[^2]。 ```cpp #include <vector> using namespace std; int minCoins(int amount, vector<int> coins) { sort(coins.begin(), coins.end(), greater<int>()); int count = 0; for(auto coin : coins){ if(amount >= coin){ count += amount / coin; amount %= coin; } if(amount == 0) break; } return amount == 0 ? count : -1; } ``` --- #### 2. 区间调度问题 描述：有多个活动的时间区间 `[s_i, e_i]`，选择最多互不重叠的活动。 核心思想：按结束时间排序并依次选取最早结束的活动[^1]。 ```python def interval_scheduling(intervals): intervals.sort(key=lambda x: x[1]) # 按照结束时间升序排列 res = [] end_time = float('-inf') for start, end in intervals: if start >= end_time: res.append((start, end)) end_time = end return res ``` --- #### 3. 分发饼干问题 描述：分发不同大小的饼干满足孩子的胃口需求，最大化满足的孩子人数。 核心思想：将孩子和饼干分别从小到大排序，优先分配最小能满足当前孩子的饼干[^5]。 ```java public int findContentChildren(int[] g, int[] s) { Arrays.sort(g); Arrays.sort(s); int child = 0, cookie = 0; while(child < g.length && cookie < s.length){ if(s[cookie] >= g[child]){ child++; } cookie++; } return child; } ``` --- #### 4. 合并石头的最低成本 描述：将 `n` 堆石子合并成一堆，每次可以选择两堆合并，目标是最小化总的代价。 核心思想：每次都取最小的两堆进行合并，利用最小堆实现优化。 ```python import heapq def stoneGameIII(stones): heap = stones.copy() heapq.heapify(heap) total_cost = 0 while len(heap) > 1: first = heapq.heappop(heap) second = heapq.heappop(heap) cost = first + second total_cost += cost heapq.heappush(heap, cost) return total_cost ``` --- #### 5. 股票买卖最佳时机 II 描述：多次买入卖出股票获取最大利润，不限制交易次数。 核心思想：只要后一天价格高于前一天即可当天买入次日卖出[^4]。 ```cpp class Solution { public: int maxProfit(vector<int>& prices) { int profit = 0; for (size_t i = 1; i < prices.size(); ++i) { if(prices[i] > prices[i-1]) profit += prices[i] - prices[i-1]; } return profit; } }; ``` --- #### 6. 最优装载问题 描述：有一批货物重量分别为 `w1,w2,...wn` 和一艘船的最大载重量为 C，问如何装载使得装入的物品总数最多？ 核心思想：按照重量从小到大排序，依次放入直到无法再放为止。 ```c++ bool cmp(const pair<int,int> &a,const pair<int,int> &b){return a.first<b.first;} int main(){ int n,C; cin>>n>>C; vector<pair<int,int>> goods(n); for(auto &[weight,id]:goods){ cin>>weight; id=++cnt; } sort(goods.begin(),goods.end(),cmp); int cnt=0,sum_weight=0; for(auto &[weight,_]:goods){ if(sum_weight+weight<=C){ sum_weight+=weight; cnt++; } else break; } cout<<cnt<<"\n"; } ``` --- #### 7. 加油站环游世界 描述：一辆汽车绕一圈经过 N 个加油站，判断是否存在起点能够顺利完成旅程。 核心思想：记录剩余油量变化趋势找到合适的起始位置。 ```python def canCompleteCircuit(gas, cost): tank = shortage = start = 0 for i in range(len(gas)): tank += gas[i] - cost[i] if tank < 0: shortage += abs(tank) start = i + 1 tank = 0 return start if tank >= shortage else -1 ``` --- #### 8. 非重复最长子串长度 描述：寻找字符串中最长不含重复字符的子串长度。 核心思想：滑动窗口配合哈希表动态维护有效范围。 ```javascript function lengthOfLongestSubstring(s) { let set = new Set(); let maxLength = 0, left = 0; for(let right = 0; right < s.length; right++) { while(set.has(s[right])) { set.delete(s[left]); left++; } set.add(s[right]); maxLength = Math.max(maxLength, right - left + 1); } return maxLength; } ``` --- #### 9. 排队打水问题 描述：N个人排队接水，每个人所需时间为 Ti 秒，计算所有人等待时间之和最小值。 核心思想：先安排耗时短的人去接水从而降低总体等待时间。 ```go func minimumWaitingTime(queries []int) int { sort.Ints(queries) total := 0 for idx, duration := range queries{ remainingQueries := len(queries)-(idx+1) total += remainingQueries * duration } return total } ``` --- #### 10. 最少硬币兑换问题 描述：给定一些面值的硬币以及一个总额度 V ，找出组成该额度所需的最少硬币数。 核心思想：采用自顶向下的递归加记忆化搜索或者迭代法解决此问题。 ```python from functools import lru_cache @lru_cache(None) def coinChange(coins, amount): if amount == 0: return 0 elif amount < 0: return -1 min_coins = float('inf') for c in coins: subproblem = coinChange(coins, amount-c) if subproblem != -1: min_coins = min(min_coins,subproblem+1) return min_coins if min_coins!=float('inf')else -1 ``` --- ###