我来帮你解决这个花园浇水次数统计问题。 ## 🧮 问题分析 - 有 n 朵花（n < 100），编号 1 到 n - 进行 q 轮浇水 - 每轮浇水区间 [L, R]（包含两端） - 需要统计每朵花最终被浇水的总次数 ## 💻 解决方案 ### 方法一：直接模拟法（适合 n 较小的情况） ```python def water_flowers(n, q, watering_ranges): """ 统计每朵花被浇水的次数 参数: n: 花朵数量 q: 浇水轮数 watering_ranges: 每轮浇水的区间列表，每个元素为 (L, R) 返回: 每朵花的浇水次数列表 """ # 初始化每朵花的浇水次数为0 flower_counts = [0] * (n + 1) # 索引从1开始，方便使用 # 模拟每轮浇水 for L, R in watering_ranges: # 确保区间在有效范围内 L = max(1, L) R = min(n, R) # 给区间内的每朵花浇水次数加1 for i in range(L, R + 1): flower_counts[i] += 1 # 返回第1到第n朵花的浇水次数 return flower_counts[1:] # 示例使用 n = 10 # 10朵花 q = 3 # 3轮浇水 watering_ranges = [(1, 5), (3, 7), (2, 6)] result = water_flowers(n, q, watering_ranges) print("每朵花的浇水次数:", result) print("详细统计:") for i, count in enumerate(result, 1): print(f"第{i}朵花: {count}次") ``` ### 方法二：差分数组法（更高效） ```python def water_flowers_diff(n, q, watering_ranges): """ 使用差分数组统计浇水次数（时间复杂度更低） """ # 创建差分数组 diff = [0] * (n + 2) # 多一个元素处理边界 # 处理每轮浇水 for L, R in watering_ranges: # 确保区间在有效范围内 L = max(1, L) R = min(n, R) # 差分数组操作 diff[L] += 1 diff[R + 1] -= 1 # 计算前缀和得到最终结果 flower_counts = [0] * (n + 1) current = 0 for i in range(1, n + 1): current += diff[i] flower_counts[i] = current return flower_counts[1:] # 测试两种方法 n = 10 q = 3 watering_ranges = [(1, 5), (3, 7), (2, 6)] print("方法一结果:", water_flowers(n, q, watering_ranges)) print("方法二结果:", water_flowers_diff(n, q, watering_ranges)) ``` ## 📊 算法比较 | 方法 | 时间复杂度 | 空间复杂度 | 适用场景 | |------|-----------|-----------|----------| | 直接模拟 | O(q × (R-L)) | O(n) | n 较小，区间较短 | | 差分数组 | O(q + n) | O(n) | 任意规模，更高效 | ## 🎯 使用示例 ```python # 完整示例 def main(): # 输入数据 n = 8 q = 4 watering_ranges = [ (1, 3), # 第1轮：浇1-3号花 (2, 5), # 第2轮：浇2-5号花 (4, 6), # 第3轮：浇4-6号花 (3, 7), # 第4轮：浇3-7号花 ] # 计算浇水次数 counts = water_flowers_diff(n, q, watering_ranges) # 输出结果 print(f"花园共有 {n} 朵花") print(f"进行了 {q} 轮浇水") print("\n浇水详情:") for i, count in enumerate(counts, 1): print(f"第{i}朵花: {count}次") # 统计信息 max_count = max(counts) min_count = min(counts) print(f"\n统计信息:") print(f"最多浇水: {max_count}次") print(f"最少浇水: {min_count}次") print(f"平均浇水: {sum(counts)/n:.2f}次") if __name__ == "__main__": main() ``` ## ⚠️ 注意事项 1. 确保输入的 L 和 R 在 1 到 n 范围内 2. 如果 n 接近 100，建议使用差分数组法 3. 可以添加输入验证确保数据有效性 ######[AI问答 | 1159点数解答 | 2026-03-20 21:36:35]