当前位置：首页 > news >正文

拆解上海市赛乙组真题：以‘轻重缓急（二）’和‘逆序对数’为例，聊聊动态规划与贪心的实战选择

news 2026/6/13 0:06:43

动态规划与贪心算法的实战抉择：从竞赛真题看策略选择

在算法竞赛中，面对复杂问题时如何选择最优解法往往比单纯掌握算法本身更为关键。本文将以两道经典竞赛题目"轻重缓急（二）"和"逆序对数"为例，深入剖析动态规划与贪心算法的适用场景与选择逻辑。

1. 算法选择的核心考量因素

算法竞赛中，面对一个问题时我们需要从多个维度评估不同解法的适用性。首要考虑的是时间复杂度与问题特征的匹配度。

以"轻重缓急（二）"为例，题目通常要求在一系列具有不同权重和紧急程度的任务中，选择最优的执行顺序以获得最大收益。这类问题往往具有以下特征：

任务间存在执行顺序的约束关系
每个任务有明确的权重和紧急度参数
最终目标是最大化某种复合指标

对于这类问题，我们通常会考虑以下解法：

算法类型	适用条件	时间复杂度	空间复杂度
贪心算法	具有贪心选择性质	O(nlogn)	O(n)
动态规划	存在最优子结构	O(n²)或O(nW)	O(nW)

关键判断点在于问题是否满足贪心选择性质。如果我们可以证明局部最优选择能导致全局最优解，那么贪心算法无疑是首选。

2. "轻重缓急（二）"的贪心解法剖析

让我们具体分析"轻重缓急（二）"的解题思路。题目通常给出n个任务，每个任务有：

处理时间t
紧急度u
权重w

目标是安排任务顺序，最小化总延迟代价或最大化某种收益。

2.1 贪心策略的建立

经过分析，我们发现当收益函数满足特定条件时，可以采用贪心策略：

def greedy_schedule(tasks): # 按照紧急度/处理时间的比值降序排列 tasks.sort(key=lambda x: x.u/x.t, reverse=True) current_time = 0 total_reward = 0 for task in tasks: current_time += task.t total_reward += task.w * max(0, task.u - current_time) return total_reward

这种排序策略背后的数学原理是：

定义任务的"单位时间紧急度"为u/t
优先处理单位时间紧急度高的任务
可以证明这种排序方式能获得最大收益

2.2 贪心选择性质的证明

要确认贪心策略的正确性，需要证明以下两点：

最优子结构：问题的最优解包含子问题的最优解
贪心选择性质：局部最优选择能导致全局最优解

对于本题，我们可以使用交换论证法：

假设存在一个最优解O与我们的贪心解G不同
找到O中第一个与G顺序不同的相邻任务对
证明交换这对任务不会降低总收益
通过有限次交换可使O变为G，且收益不减

3. "逆序对数"的动态规划解法

相比之下，"逆序对数"问题则更适合动态规划解法。题目通常要求计算一个序列中逆序对的数量，即i < j且a[i] > a[j]的(i,j)对数。

3.1 暴力解法的局限

最直观的解法是双重循环：

def count_inversions_naive(arr): inv_count = 0 n = len(arr) for i in range(n): for j in range(i+1, n): if arr[i] > arr[j]: inv_count += 1 return inv_count

这种解法时间复杂度为O(n²)，对于大规模数据(n>1e5)显然不够高效。

3.2 基于分治的优化解法

我们可以采用分治法将复杂度降至O(nlogn)：

def count_inversions(arr): # 归并排序过程中统计逆序数 if len(arr) <= 1: return arr, 0 mid = len(arr) // 2 left, inv_left = count_inversions(arr[:mid]) right, inv_right = count_inversions(arr[mid:]) merged, inv_merge = merge(left, right) total = inv_left + inv_right + inv_merge return merged, total def merge(left, right): result = [] i = j = 0 inv_count = 0 while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 inv_count += len(left) - i result.extend(left[i:]) result.extend(right[j:]) return result, inv_count

这种解法虽然高效，但本质上仍是基于分治的计数方法，而非典型的动态规划。

3.3 动态规划视角的理解

从DP角度，我们可以将问题重新建模：

定义dp[i]为前i个元素中的逆序对数
状态转移方程为： dp[i] = dp[i-1] + (a[0..i-1]中大于a[i]的元素个数)
使用二叉索引树(Fenwick Tree)高效计算后半部分

class FenwickTree: def __init__(self, size): self.size = size self.tree = [0] * (self.size + 1) def update(self, index, delta=1): while index <= self.size: self.tree[index] += delta index += index & -index def query(self, index): res = 0 while index > 0: res += self.tree[index] index -= index & -index return res def count_inversions_dp(arr): # 坐标压缩 sorted_arr = sorted(set(arr)) rank = {v: i+1 for i, v in enumerate(sorted_arr)} ft = FenwickTree(len(sorted_arr)) inv_count = 0 for num in reversed(arr): r = rank[num] inv_count += ft.query(r - 1) ft.update(r) return inv_count

这种解法展示了DP思想在高效计数问题中的应用，时间复杂度O(nlogn)。