登录以参加训练计划

一、什么是贪心算法？

贪心算法（Greedy Algorithm）像一只​​永远盯着眼前最大块蛋糕的吃货​​🐷，每一步都选择​​当前最优解​​，希望最终得到全局最优解。在信息学奥赛中，它是解决最优化问题的利器，尤其适合那些​​局部最优能推导出全局最优​​的场景。

贪心三要素​​： ​​1. 贪心选择性质​​：当前最优解能导致全局最优。 2. 无后效性​​：选择后不会影响后续决策。 ​​3. 局部最优 → 全局最优​​（关键！） 4. 高效性​​：时间复杂度通常为O(nlogn)或更低

二、贪心算法的经典题型​

1.活动安排问题.

题目​​：选最多不重叠活动（如会议、课程） ​​贪心策略​​：按​​结束时间排序​​，优先选早结束的留时间给更多活动！

#include <iostream>
#include <algorithm>
using namespace std;

struct Activity { 
    int start, end;
    bool operator<(const Activity &a) const { 
        return end < a.end;  // 按结束时间排序
    }
};

int main() {
    int n;
    cin >> n;
    Activity activities[n];
    for(int i=0; i<n; ++i) 
        cin >> activities[i].start >> activities[i].end;
    
    sort(activities, activities+n);
    
    int count = 1, lastEnd = activities[0].end;
    for(int i=1; i<n; ++i) {
        if(activities[i].start >= lastEnd) {
            count++;
            lastEnd = activities[i].end;
        }
    }
    cout << count << endl;
    return 0;
}

2.加油站问题.

题目​​：汽车能否绕环路一周？找到可行起点 ​​贪心策略​​： 总油量不足直接返回-1 局部油量不足则重置起点

#include <bits/stdc++.h>
using namespace std;

int GetStation(int gas[], int cost[], int n) {
    int total = 0, cur = 0, start = 0;
    for(int i=0; i<n; ++i) {
        total += gas[i] - cost[i];
        cur += gas[i] - cost[i];
        if(cur < 0) {        // 当前油量不足
            start = i + 1;   // 重置起点
            cur = 0;
        }
    }
    return total >=0 ? start : -1;
}

3.均分纸牌问题​.

题目​​：用最少次数使多堆纸牌数量相等. ​​贪心策略​​： 从左到右传递差值！每个位置只需处理与平均值的差值

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, s=0, ans=0;
    cin >> n;
    vector<int> a(n);
    for(int i=0; i<n; ++i) {
        cin >> a[i];
        s += a[i];
    }
    int avg = s / n, t = 0;
    for(int i=0; i<n-1; ++i) {
        t += a[i] - avg;
        if(t != 0) ans++;  // 需要调整
    }
    cout << ans << endl;
    return 0;
}

三，贪心 VS DP

贪心算法就像​​玩俄罗斯方块​​——每一步都要选择​​当前最合适的方块位置​​才能得高分！ 记住： ​​排序是贪心的灵魂​​（80%的题需要先排序） ​​验证策略的正确性​​（数学归纳或反证法） ​​多刷题培养直觉​​（区间类、资源分配类优先） ​​贪心不是真贪心，而是聪明的选择！​​