登录以参加训练计划

贪心算法核心知识点与应用

针对信息学竞赛的贪心算法系统总结

一、贪心算法基础

1.1 贪心算法思想

• 核心思想：每一步选择当前状态下的最优解
• 适用条件：
  • 问题具有最优子结构
  • 问题具有贪心选择性质
• 实现步骤：
  1. 建立数学模型
  2. 分解问题为子问题
  3. 定义贪心选择策略
  4. 证明贪心选择的正确性

1.2 贪心算法特点

特点	说明	示例
高效性	时间复杂度通常较低	O(n log n)
局部最优	每次选择局部最优解	短作业优先
不可回溯	选择后不可更改	活动选择
简单实现	代码通常简洁	中位数问题

二、经典贪心问题分类与策略

2.1 排序优化类问题

核心策略：通过排序使问题满足贪心条件

2.1.1 排队打水问题

• 问题特征：多资源调度
• 贪心策略：
  1. 按打水时间升序排序
  2. 将短作业优先分配到空闲资源
• 关键代码：

  sort(times, times + n); // 升序排序
  for (int i = 0; i < n; i++) {
      // 分配到最早空闲的水龙头
  }
  

2.1.2 活动选择问题

• 问题特征：区间不重叠最大化
• 贪心策略：
  1. 按结束时间升序排序
  2. 选择最早结束且不冲突的活动
• 数学原理：最早结束的活动留下最多时间资源

2.2 策略选择类问题

核心策略：比较多种策略选择最优

2.2.1 过河的最短时间

• 问题特征：多人协作优化
• 贪心策略：
  1. 按过河时间升序排序
  2. 每次处理最慢两人：
     • 策略1：最快带最慢，最快返回
     • 策略2：最快两人过，最快返回；最慢两人过，次快返回
  3. 选择耗时更少的策略

2.2.2 删数问题

• 问题特征：字典序最小化
• 贪心策略：
  1. 从左到右扫描数字
  2. 移除比后一位大的数字（去"峰"）
  3. 确保移除s个数字
• 关键点：处理前导零和边界情况

2.3 位置优化类问题

核心策略：利用数学性质直接求解

2.3.1 最佳位置问题

• 问题特征：距离和最小化
• 贪心策略：
  1. 按位置升序排序
  2. 选择中位数位置
• 数学证明：中位数使绝对偏差最小

2.4 序列覆盖类问题

核心策略：动态维护最优状态

2.4.1 拦截导弹系统

• 问题特征：非上升序列覆盖
• 贪心策略：
  1. 维护系统可拦截高度
  2. 对于每个导弹：
     • 选择能拦截的最小高度系统
     • 若无合适系统，创建新系统
• 算法优化：O(n log n) 使用二分查找

2.4.2 导弹拦截方案

• 问题特征：方案构造
• 贪心策略：
  1. 记录每个系统的拦截序列
  2. 选择最后高度最小的合适系统
  3. 更新系统状态

2.5 资源分配类问题

核心策略：性价比优先原则

2.5.1 购买贺年卡

• 问题特征：最小化总花费
• 贪心策略：
  1. 按单价升序排序
  2. 优先从低价商家购买
  3. 依次满足需求

三、贪心算法实现技巧

3.1 排序技巧

排序目的	排序方式	应用问题
时间优化	升序排序	打水问题
结束时间		活动选择
位置优化		最佳位置
单价优化		购买贺卡

3.2 策略比较技巧

graph TD
    A[分析问题] --> B[识别策略]
    B --> C[实现策略1]
    B --> D[实现策略2]
    C --> E[计算策略1结果]
    D --> F[计算策略2结果]
    E --> G[比较结果]
    F --> G
    G --> H[选择最优策略]

3.3 状态维护技巧

1. 数组标记法：使用数组记录系统状态

   int systems[MAX]; // 存储每个系统最后拦截高度
   int count = 0;    // 系统计数
   

2. 指针跟踪法：使用指针记录关键位置

   int last = 0; // 记录最后选择位置
   

四、贪心算法应用总结

4.1 问题特征与策略选择

问题类型	特征	贪心策略	时间复杂度
调度优化	多资源分配	短作业优先	O(n log n)
路径优化	多人协作	策略比较
位置优化	距离最小	中位数
序列覆盖	非上升序列	系统维护	O(n²)
字典序优化	数字序列	去峰法	O(n)
资源分配	最小花费	单价优先	O(n log n)

4.2 贪心算法局限性

1. 非全局最优：局部最优不一定全局最优
2. 证明困难：正确性证明常是难点
3. 适用范围窄：需满足贪心选择性质
4. 无法回溯：选择后无法撤销

五、经典题目代码框架

5.1 最佳位置问题

#include <stdio.h>
#include <stdlib.h>

int cmp(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}

int main() {
    int n;
    scanf("%d", &n);
    int positions[n];
    
    for (int i = 0; i < n; i++) {
        scanf("%d", &positions[i]);
    }
    
    qsort(positions, n, sizeof(int), cmp);
    
    int median = positions[n/2]; // 中位数位置
    int total_distance = 0;
    
    for (int i = 0; i < n; i++) {
        total_distance += abs(positions[i] - median);
    }
    
    printf("%d\n", total_distance);
    return 0;
}

5.2 拦截导弹系统数量

#include <stdio.h>

int main() {
    int n, count = 0;
    scanf("%d", &n);
    int missiles[n];
    int systems[n]; // 记录每个系统最后拦截高度
    
    for (int i = 0; i < n; i++) {
        scanf("%d", &missiles[i]);
    }
    
    for (int i = 0; i < n; i++) {
        int found = 0;
        int min_index = -1;
        int min_value = 30001;
        
        // 查找合适系统
        for (int j = 0; j < count; j++) {
            if (systems[j] >= missiles[i] && systems[j] < min_value) {
                min_value = systems[j];
                min_index = j;
                found = 1;
            }
        }
        
        if (found) {
            systems[min_index] = missiles[i];
        } else {
            systems[count] = missiles[i];
            count++;
        }
    }
    
    printf("%d\n", count);
    return 0;
}

5.3 删数问题

#include <stdio.h>
#include <string.h>

int main() {
    char num[1001];
    int s;
    scanf("%s %d", num, &s);
    
    int len = strlen(num);
    int remove_count = 0;
    
    while (s > 0) {
        int i = 0;
        // 找到第一个比后一位大的数字
        while (i < len - 1 && num[i] <= num[i+1]) {
            i++;
        }
        
        // 删除找到的数字
        for (int j = i; j < len - 1; j++) {
            num[j] = num[j+1];
        }
        len--;
        s--;
    }
    
    // 去除前导零
    int start = 0;
    while (start < len && num[start] == '0') {
        start++;
    }
    
    // 输出结果
    if (start == len) {
        printf("0\n");
    } else {
        for (int i = start; i < len; i++) {
            printf("%c", num[i]);
        }
        printf("\n");
    }
    
    return 0;
}

六、学习建议与资源

6.1 学习路径

1. 基础掌握：排序类贪心问题（打水、活动选择）
2. 进阶训练：策略选择类问题（过河、删数）
3. 综合应用：序列覆盖类问题（导弹拦截）
4. 难题挑战：动态规划与贪心结合问题

6.2 训练方法

1. 一题多解：比较贪心与其他算法优劣
2. 边界测试：测试特殊输入情况
3. 复杂度分析：评估算法效率
4. 正确性证明：练习数学证明

"贪心算法是信息学竞赛的利器，掌握核心问题模型和策略选择技巧，配合系统训练，定能取得突破！"