基于数组的独特行程选择最优算法及可行行程计数咨询

嘿，我来帮你拆解这个问题，先把场景和例子说清楚，再给你最优的解法思路。

问题核心约束明确 #

先把你描述的规则拆解成清晰的条件：

• 三个等长数组：parks（主题公园距离）、museums（博物馆距离）、beaches（海滩距离）
• 行程必须按固定顺序选择：先选一个主题公园，再选一个博物馆，最后选一个海滩（三类各一个）
• 全程不倒车：选中的三个距离必须满足 park_dist < museum_dist < beach_dist（沿着公路向前开，每一步都往远离起点的方向走，不能回头）
• 不重复访问同一景点：只要不从同一个数组里重复选元素就行（比如博物馆的37和海滩的37是不同景点，不算重复）

例子解读 #

你给出的示例数组：

• parks = [29, 50]
• museums = [61, 37]
• beaches = [37, 70]

我们只需要筛选出满足park < museum < beach的三元组：

1. 29（公园）→37（博物馆）→70（海滩）：29 < 37 < 70 ✅
2. 29（公园）→61（博物馆）→70（海滩）：29 < 61 < 70 ✅
3. 50（公园）→61（博物馆）→70（海滩）：50 < 61 < 70 ✅

剩下的5种组合要么不满足递增关系（比如29→61→37，61>37属于倒车），要么先选了更远的博物馆再选近的（比如50→37→70，50>37不符合顺序递增），都被排除，所以最终返回3，完全符合你的描述。

最优算法思路 #

如果直接暴力枚举所有三元组（时间复杂度O(n³)，n是数组长度），当n很大时（比如n=1000），效率会非常低。我们可以通过排序+二分查找把时间复杂度降到O(n² log n)，甚至优化到O(n log n)，具体步骤如下：

步骤1：排序预处理 #

先把museums和beaches数组分别排序，这样我们可以用二分查找快速找到符合条件的元素数量：

• 排序后的museums：[37, 61]
• 排序后的beaches：[37, 70]

步骤2：基础实现（O(n² log n)） #

import bisect

def count_valid_trips(parks, museums, beaches):
    # 排序预处理
    museums_sorted = sorted(museums)
    beaches_sorted = sorted(beaches)
    total = 0
    
    for p in parks:
        # 找到第一个大于p的博物馆索引
        m_idx = bisect.bisect_right(museums_sorted, p)
        # 遍历所有符合条件的博物馆
        for m in museums_sorted[m_idx:]:
            # 找到第一个大于m的海滩索引
            b_idx = bisect.bisect_right(beaches_sorted, m)
            total += len(beaches_sorted) - b_idx
    return total

# 测试示例
parks = [29, 50]
museums = [61, 37]
beaches = [37, 70]
print(count_valid_trips(parks, museums, beaches))  # 输出3

进一步优化（O(n log n)） #

如果n很大，上面的O(n² log n)还是有点慢，我们可以先对museums和beaches做预处理，提前计算每个博物馆对应的符合条件的海滩数量，再用前缀和快速累加：

import bisect

def count_valid_trips_optimized(parks, museums, beaches):
    museums_sorted = sorted(museums)
    beaches_sorted = sorted(beaches)
    n = len(beaches_sorted)
    
    # 预处理：每个博物馆对应的符合条件的海滩数量
    beach_counts = []
    for m in museums_sorted:
        b_idx = bisect.bisect_right(beaches_sorted, m)
        beach_counts.append(n - b_idx)
    
    # 构建前缀和数组，方便快速累加区间和
    prefix_sum = [0] * (len(beach_counts) + 1)
    for i in range(len(beach_counts)):
        prefix_sum[i+1] = prefix_sum[i] + beach_counts[i]
    
    total = 0
    for p in parks:
        # 找到所有大于p的博物馆的起始索引
        m_idx = bisect.bisect_right(museums_sorted, p)
        # 累加这些博物馆对应的海滩数量总和
        total += prefix_sum[-1] - prefix_sum[m_idx]
    return total

这个优化后的版本在n很大时会快很多，比如n=1000的话，O(n log n)比O(n² log n)效率提升近1000倍。

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