简单贪心笔记

---

题1：P2027 当总统

题型定位

入门贪心 | 最小代价优先 | 排序基础应用题

核心考点

• 贪心核心策略：最小代价优先，用最少成本达成目标
• 升序排序的基础应用
• 整数除法的边界处理、多组测试用例的变量初始化

题目大意

小明竞选总统，需要获得超过一半的州的支持才能当选；每个州中，需要获得超过一半的选民支持，才能赢得该州。给出每个州的选民人数，求小明当选总统至少需要赢得多少选民的支持。

贪心核心思路

1. 要最小化总选民数，必须优先拿下选民最少的州（拿下每个州的成本更低）；
2. 要超过半数的州，最少需要拿下 m/2 + 1 个州（m为州总数，奇偶均适用）；
3. 对每个州，拿下它所需的最少选民数为 该州选民数/2 + 1（超过半数，整数除法向下取整）；
4. 对所有州的选民数升序排序，取前m/2 + 1个州，累加每个州的最小成本即可。

AC代码

#include<bits/stdc++.h>
using namespace std;
#define int long long // 防数据溢出，统一用long long
int n,m,a[110]; // n组测试用例，m为州数，a存储每个州的选民数
signed main(){
    cin>>n;
    while(n--){ // 处理多组测试用例
        cin>>m;
        for(int i=1;i<=m;i++){
            cin>>a[i];
        }
        int ans=0;
        sort(a+1,a+1+m); // 升序排序，优先选选民最少的州
        // 取超过半数的州：m/2+1个，保证当选
        for(int i=1;i<=m/2+1;i++){
            ans+=a[i]/2+1; // 累加拿下该州的最小选民数
        }
        cout<<ans<<"\n";
    }
    return 0;
}

关键代码解析

1. sort(a+1,a+1+m)：升序排序是贪心的核心，保证我们能以最低成本拿到足够的州；
2. m/2 + 1：无论m是奇数还是偶数，都能保证州的数量超过半数。例：m=3，取2个；m=6，取4个；
3. a[i]/2 + 1：整数除法自动向下取整，完美实现“超过半数”的要求，例：5个选民，5/2+1=3，刚好超过半数。

易错点&复习提醒

• 多组测试用例中，ans必须在每组循环内初始化，否则会累加前一组的结果，导致答案错误；
• 数组下标注意：代码从1开始存储，sort的结束位置是a+1+m，不要写成a+m导致最后一个元素未排序；
• 数据范围：本题m≤101，选民数≤100，无需担心溢出，但养成用long long的习惯，避免后续大数据题踩坑。

---

题2：P2521 纪念品分组

题型定位

经典贪心 | 双指针贪心 | 最优装载问题模板题

核心考点

• 贪心核心策略：最大+最小配对优先，最大化每组利用率
• 排序+双指针算法
• 最少分组问题的经典模型

题目大意

有n件纪念品，每件有一个价格，每组最多放2件纪念品，且每组的总价不能超过上限w。求最少需要分成多少组，才能装完所有纪念品。

贪心核心思路

1. 要让分组数最少，就要尽可能让每组都装2件，减少单独成组的情况；
2. 对所有纪念品价格升序排序，左指针l指向当前最便宜的纪念品，右指针r指向当前最贵的纪念品；
3. 若最便宜+最贵的总价≤w：两人同组，l右移，r左移，组数+1；
4. 若总价超过w：最贵的纪念品无法和任何其他纪念品同组，只能单独成组，r左移，组数+1；
5. 循环直到l>r，所有纪念品处理完毕。

AC代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,a[300010],w,ans; // w为每组总价上限，ans为分组数
signed main(){
    cin>>w>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+1+n); // 升序排序，为双指针配对做准备
    int l=1,r=n; // 左指针：当前最便宜，右指针：当前最贵
    while(l<=r){
        if(a[l]+a[r]<=w){ // 可以配对，同组
            ans++;
            l++;
            r--;
        }else{ // 无法配对，最贵的单独成组
            ans++;
            r--;
        }
    }
    cout<<ans;
    return 0;
}

关键代码解析

1. 排序是双指针贪心的前提：只有有序数组，才能保证“最大+最小”的配对策略能得到全局最优解；
2. 循环条件l<=r：当l==r时，只剩最后一件纪念品，会进入else分支，单独成组，不会遗漏；
3. 时间复杂度：排序O(nlogn)，双指针遍历O(n)，整体O(nlogn)，能轻松处理n≤3e5的大数据范围。

易错点&复习提醒

• 循环边界必须是l<=r，不能写成l<r，否则会漏掉最后一件纪念品，导致答案少1；
• 本题严格限制每组最多2件，此贪心策略仅适用于该场景，不可直接套用到每组可装多件的场景；
• 数组大小要开够，本题n最大3e5，必须开3e5以上的数组，避免数组越界。

---

题3：T1262 [GESP202312 四级T2] 田忌赛马

题型定位

经典贪心 | 最优胜负配对 | 排序匹配模板题

核心考点

• 贪心核心策略：用最小的代价赢下对方，最大化获胜场次
• 双数组排序+贪心匹配
• GESP/CSP-J高频考点

题目大意

你和田忌各有n匹马，每匹马有唯一的速度，速度快的马会赢得比赛。你可以自由安排自己马的出场顺序，求最多能赢田忌多少场比赛。

贪心核心思路

1. 要最大化获胜场次，就要用刚好能赢对方的最慢的马去赢，避免用快马赢对方的慢马，浪费战力；
2. 将你的马（a数组）和田忌的马（b数组）都升序排序；
3. 用双指针匹配：遍历你的马，若当前你的马能赢田忌当前最慢的未匹配的马，就赢下这一场，田忌的指针后移，获胜场次+1；
4. 若赢不了，就用这匹马去消耗田忌更快的马，不浪费赢的机会。

AC代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,a[50010],b[50010],sb=1,ans; // sb是田忌马的指针，ans是获胜场次
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i]; // 你的马的速度
    }
    for(int i=1;i<=n;i++){
        cin>>b[i]; // 田忌的马的速度
    }
    sort(a+1,a+1+n); // 你的马升序排序
    sort(b+1,b+1+n); // 田忌的马升序排序
    for(int i=1;i<=n;i++){
        // 用当前最小的能赢的马，赢田忌当前最慢的马
        if(a[i]>b[sb]){
            sb++;
            ans++;
        }
    }
    cout<<ans;
    return 0;
}

关键代码解析

1. 双升序排序：保证我们能从小到大依次匹配，用最小的代价赢下比赛，实现赢场最大化；
2. 核心匹配逻辑a[i]>b[sb]：只有当你的马能赢田忌当前未匹配的最慢的马时，才选择赢下，避免浪费快马；
3. 时间复杂度：排序O(nlogn)，遍历O(n)，整体O(nlogn)，适配n≤5e4的范围。

易错点&复习提醒

• 本代码是基础核心版，仅实现“最大化赢场”的最简贪心，完整的田忌赛马还需要处理平局、用最慢的马消耗对方最快的马的场景，进阶复习时需掌握完整版；
• 两个数组必须都排序，且排序方向一致，否则贪心策略失效；
• 指针sb的初始值必须和数组起始下标一致（本题从1开始），避免匹配错位。

---

题4：P2526 蜡烛

题型定位

入门贪心 | 模拟枚举贪心 | 排序应用题

核心考点

• 贪心核心策略：降序排序优先用最长的蜡烛，保证坚持最久
• 降序排序+模拟枚举
• 边界条件判断

题目大意

有n根蜡烛，每根蜡烛的长度为a[i]，每根蜡烛每燃烧1小时会减少1单位长度。第1天需要点燃1根蜡烛，第2天需要点燃2根蜡烛，……，第k天需要点燃k根蜡烛，每天点燃的蜡烛必须持续燃烧1小时。请问你最多能连续坚持多少天？

贪心核心思路

1. 要坚持最久，每天都要优先用当前最长的蜡烛，避免短蜡烛提前用完，导致后续无法凑够数量；
2. 枚举天数k（代码中为ni），从1开始依次尝试；
3. 每次枚举前，将蜡烛长度降序排序，检查前k根蜡烛是否都能燃烧1小时（长度>0）；
4. 若可以，将前k根蜡烛各减1，继续尝试下一天；若不行，说明最多能坚持k-1天，结束枚举。

AC代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,a[60];
// 降序排序比较函数，保证每次排序后，蜡烛长度从长到短排列
bool cmp(int s1,int s2){
    return s1>s2;
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i]; // 每根蜡烛的长度
    }
    int day=0; // 枚举当前尝试的天数
    while(day<=n){ // 最多坚持n天（第n天需要n根蜡烛，超过n根不可能）
        day++;
        sort(a+1,a+1+n,cmp); // 降序排序，优先用最长的蜡烛
        bool ok=1; // 标记当天是否能坚持
        // 检查前day根蜡烛是否都能燃烧1小时
        for(int i=1;i<=day;i++){
            if(a[i]==0){
                ok=0;
                break;
            }
        }
        if(!ok)break; // 无法坚持，退出循环
        // 当天可以坚持，前day根蜡烛各燃烧1小时
        for(int i=1;i<=day;i++)a[i]--;
    }
    cout<<day-1; // 最多能坚持的天数
    return 0;
}

关键代码解析

1. 降序排序：每次枚举天数前都降序排序，保证我们优先使用最长的蜡烛，最大化蜡烛的利用率，是贪心策略的核心；
2. 枚举边界day<=n：第k天需要k根蜡烛，而总共有n根蜡烛，所以最多只能坚持n天，避免无效枚举；
3. 核心判断：只有前day根蜡烛都>0，才能满足当天的需求，否则无法坚持。

易错点&复习提醒

• 排序的比较函数cmp必须是降序，若写成升序，会优先用短蜡烛，导致答案偏小，直接错误；
• 最终输出的是day-1，因为循环中day先自增，再判断是否能坚持，无法坚持时，最后一次有效的天数是day-1；
• 本代码是暴力模拟版，适合n≤60的小数据范围，进阶复习时需掌握O(nlogn)的二分优化版，适配更大的数据范围。

---

4道贪心题 核心考点汇总表

洛谷题号	题目名称	核心贪心策略	排序方向	核心算法结构	难度
P2027	当总统	最小代价优先，用最低成本达成目标	升序	排序+前缀累加	3
P2521	纪念品分组	最大+最小配对，最大化每组利用率		排序+双指针
T1262	田忌赛马	最小代价赢对方，最大化获胜场次	双升序	排序+双指针匹配	2
P2526	蜡烛	降序优先用最长的，保证坚持最久	降序	排序+枚举模拟	3

复习核心提醒

1. 贪心算法的核心是局部最优推导出全局最优，每道题的排序都是为了给贪心策略提供基础，必须先理解“为什么这个贪心策略是对的”，再背诵代码；
2. 所有模板题的三大易错点：数组下标、循环边界、多组用例的变量初始化，这是考试中最容易丢分的地方，复盘时重点检查；
3. 入门阶段先掌握模板代码，再逐步拓展优化版和变体题型，循序渐进提升贪心思维。