如何用动态规划解决HackerRank Cloudy Day问题？我的代码为何报错？

一座城市有多个城镇。p是n个城镇的人口数组，x是城镇在一维数组上的位置数组（数值型位置），y是云的位置数组，r是云的覆盖范围数组。处于云下的城镇人口处于黑暗区域，其余人口处于晴朗区域。第i朵云覆盖位置在[y[i]-r[i], y[i]+r[i]]范围内的所有城镇。城市拥有只能驱散一朵云的技术，请编写函数返回驱散任意一朵云后，能确保处于晴朗区域的最大人口数。

以下是我的尝试（含行内注释）：

from collections import defaultdict 

def maximumPeople(p, x, y, r):
       
    loc2cloudy = defaultdict(bool) 
    
    for c in range(len(y)): # mapping location to if it is cloudy
        for r_i in range(y[c]-r[c],y[c]+r[c]+1):
            loc2cloudy[r_i] = True 
            
    # print(dict(loc2cloudy))
    
    sunny_popn_count = 0 # population not under any clound
    
    loc2popn = defaultdict(int)
    
    for t in range(len(x)): # mapping location to its population
        loc2popn[x[t]] += p[t]
        if loc2cloudy[x[t]] == False:
            sunny_popn_count += p[t] 
        
    # print(dict(loc2popn))
    
    max_cloud_popn = 0
    
    for c in range(len(y)): 
        cloud_popn = 0
        for r_i in range(y[c]-r[c],y[c]+r[c]+1): # finding population under cloud
            cloud_popn += loc2popn[r_i]     

        max_cloud_popn = max(max_cloud_popn, cloud_popn) 

    # print('{}:{}'.format(t, sunny_popn_count))
            
    return sunny_popn_count + max_cloud_popn

在27个测试用例中，我的代码仅通过2个，失败2个，其余均为运行时错误。请问我哪里出错了？同时想了解如何用动态规划解决该问题。

一、你的代码错误点 #

1. 遍历范围的致命问题
   你用range(y[c]-r[c], y[c]+r[c]+1)遍历云覆盖的所有位置，但题目中城镇的位置x是数值型，可能是极大的整数（比如1e9），甚至是浮点数。当云的覆盖范围很大时（比如r[i]是1e9），这个循环会执行数十亿次，直接导致超时或内存溢出，这就是大部分测试用例出现运行时错误的核心原因。

2. 重复计算的逻辑漏洞
   你统计cloud_popn时，把所有被当前云覆盖的城镇人口都算进去，但如果某个城镇被多朵云覆盖，驱散当前云后这个城镇仍然处于黑暗中，这部分人口不应该被加到结果里。你的代码会错误地重复计算这部分人口，导致结果偏大。

二、动态规划思路的解法 #

这个问题的核心是统计每个城镇被多少朵云覆盖，然后区分：

• 完全不被任何云覆盖的人口（始终晴朗）
• 只被某一朵云覆盖的人口（驱散该云后会变晴朗）

我们可以通过事件点排序+状态维护（类似动态规划的状态转移）来高效解决，步骤如下：

1. 预处理事件点

   • 将每朵云的覆盖区间[y[i]-r[i], y[i]+r[i]]拆成两个事件：(y[i]-r[i], +1, 云索引)（云开始覆盖）和(y[i]+r[i]+1, -1, 云索引)（云结束覆盖）。
   • 将城镇的位置和人口整理为事件：(x[j], p[j])。

2. 排序事件点
   按位置从小到大排序，同位置的事件按优先级处理：先处理云结束事件，再处理城镇人口事件，最后处理云开始事件（确保区间边界的统计准确）。

3. 遍历事件维护状态

   • 维护current_clouds变量，记录当前位置被多少朵云覆盖；维护current_single_cloud变量，记录当current_clouds=1时唯一覆盖的云的索引。
   • 遍历排序后的事件：
     • 遇到云事件时，更新current_clouds，并同步更新current_single_cloud。
     • 遇到城镇事件时：
       • 若current_clouds == 0，将人口加入total_sunny（始终晴朗的人口）。
       • 若current_clouds == 1，将人口加入对应云的unique_pop数组（只被该云覆盖的人口）。
       • 若current_clouds > 1，这部分人口无论驱散哪朵云都仍处于黑暗，忽略。

4. 计算最终结果
   找到unique_pop中的最大值，最终结果为total_sunny + max_unique_pop。

三、优化后的代码示例 #

def maximumPeople(p, x, y, r):
    events = []
    # 添加云的开始/结束事件
    for cloud_idx in range(len(y)):
        start = y[cloud_idx] - r[cloud_idx]
        end = y[cloud_idx] + r[cloud_idx] + 1
        events.append((start, 'cloud', +1, cloud_idx))
        events.append((end, 'cloud', -1, cloud_idx))
    
    # 添加城镇人口事件
    for town_idx in range(len(x)):
        events.append((x[town_idx], 'town', p[town_idx], town_idx))
    
    # 排序规则：位置升序；同位置时，云结束事件优先，然后是城镇，最后是云开始
    events.sort(key=lambda e: (e[0], 0 if e[2] == -1 else 1 if e[1] == 'town' else 2))
    
    total_sunny = 0
    cloud_unique_pop = [0] * len(y)
    current_clouds = 0
    current_single_cloud = -1
    
    for event in events:
        pos, typ, val, idx = event
        if typ == 'cloud':
            prev_clouds = current_clouds
            current_clouds += val
            # 更新唯一覆盖的云的索引
            if prev_clouds == 1:
                current_single_cloud = -1
            elif current_clouds == 1:
                current_single_cloud = idx
        else:
            # 处理城镇人口
            if current_clouds == 0:
                total_sunny += val
            elif current_clouds == 1:
                cloud_unique_pop[current_single_cloud] += val
    
    max_unique = max(cloud_unique_pop) if cloud_unique_pop else 0
    return total_sunny + max_unique

该解法时间复杂度为O((N+M)log(N+M))（N为城镇数，M为云数），能高效处理大规模输入，避免了原代码的遍历范围问题和逻辑漏洞。

内容的提问来源于stack exchange，提问作者MsA