前言贪心算法的学习重点我想放在见多识广上轻证明甚至不证明如果一道题你没有任何思路不妨想想贪心能不能做当然其实我们能想到的贪心策略取决于我们做过多少道题。一般就是题目里说求什么最少什么最大的时候可以想想贪心。P10452 货仓选址 - 洛谷货仓建在中点(下标的中点)的时候到每家商店的距离之和最小。由于题目给出的坐标是乱序的但这里说的中点是有序之后下标的中点因此需要排序一下才能找到中点的位置在哪中点的计算方式就是(1 n) / 2。贪心策略想出来之后可以多举几个例子来看看对不对就比如照这道题的题目样例来看的话无论是货仓建在(a[1] a[n]) / 2的位置上还是a[(1 n) / 2]上都对但是你换个例子就发现后者才是对的。#includeiostream using namespace std; #includealgorithm const int N 1e5 10; int a[N]; int n; int main() { cin n; for(int i 1;i n;i) cin a[i]; sort(a 1, a 1 n); long long ret 0; int mid (1 n) / 2; for(int i 1;i n;i) { ret abs(a[i] - a[mid]); } cout ret endl; return 0; }P1115 最大子段和 - 洛谷这题之前用的是前缀和来做的这次用贪心来做。题目的意思就是求最大子段和那我们就可以从前往后累加到变量sum里当sum0时一直累加每加一次就更新一下结果。当sum0时直接舍弃掉前边累加过的所有sum清零之后从当前位置的下一个位置开始加。#includeiostream using namespace std; typedef long long LL; const int N 2e5 10; int a[N]; int n; LL sum; int main() { cin n; for(int i 1;i n;i) cin a[i]; LL ret -1e7; for(int i 1;i n;i) { sum a[i]; ret max(ret, sum); if(sum 0) sum 0; } cout ret; return 0; }P1094 [NOIP 2007 普及组] 纪念品分组 - 洛谷#includeiostream using namespace std; #includealgorithm const int N 3e4 10; int a[N]; int w, n; int 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; int ret 0; while(l r) { if(a[l] a[r] w) { l; --r; } else { --r; } //不管是不是w的都要更新结果 //因为分组可以一组两个 也可以一组一个 ret; } cout ret; return 0; }P1056 [NOIP 2008 普及组] 排座椅 - 洛谷#includeiostream using namespace std; #includealgorithm const int N 1010; struct s { int index;//表示第i条横向/纵向通道 int cnt;//第i条通道所隔开的同学的对数 }cow[N], col[N]; int m, n, k, l, d; bool comp1(s s1, s s2) { return s1.cnt s2.cnt; } bool comp2(s s1, s s2) { return s1.index s2.index; } int main() { cin m n k l d; //初始化结构体 //cow[i]表示一个s因为cow是数组 for(int i 1;i m;i) cow[i].index i; for(int i 1;i n;i) col[i].index i; while(d--) { int x, y, p, q; cin x y p q; //横坐标相同划列通道 //第i条通道表示的是在第i列和第i1列之间所以要取min if(xp) col[min(y, q)].cnt; else if(yq) cow[min(x, p)].cnt; } //排序取前k个和前l个cnt最大的 sort(cow 1, cow 1 m, comp1); sort(col 1, col 1 n, comp1); //输出前得先将前k个和前l个按照index排序从小到大输出 sort(cow 1, cow 1 k, comp2); sort(col 1, col 1 l, comp2); //输出按照index输出 for(int i 1;i k;i) cout cow[i].index ; cout endl; for(int i 1;i l;i) cout col[i].index ; return 0; }矩阵消除游戏这题一读完一定会想到一种贪心解法就是将当前矩阵所有的行和和所有的列和都算出来取最大值所在的那一行/那一列然后将该行/列清0之后继续重复上述思路但其实这样的贪心策略是错误的和第一题一样当你不确定的时候可以多举几个例子来看看你的贪心策略到底对不对但是考试的时候其实就没招了你试试贪心算法哪怕是错的也能捞点分。对于这题当贪心策略发生问题的时候就需要想想别的方式其实这里很明显会发现你选择了一行/列之后将其清0那不就影响到了其他行/列的和了其实如果会产生影响的话贪心就大概率是错的由于题目范围给出的矩阵的行数列数15所以可以想一想暴力解法既然刚才说行的取法会影响到列那我就先选择行的取法每一行要么就是选要么就是不选那我们就用二进制枚举的方式先固定住行的选法然后就贪心的选择列就是行固定选法之后取列最大的。根据题目意思选择的行数和列数之和k因为k的范围有可能是要比nm大的nm就是矩阵的行数列数之和。#includeiostream using namespace std; #includealgorithm const int N 25; int n, m, k; int a[N][N]; //统计x里1的个数 int calc(int x) { int cnt 0; while(x) { cnt; x x (x - 1); } return cnt; } bool comp(int x, int y) { return x y; } int main() { cin n m k; //矩阵下标得从0开始存数据不然跟二进制枚举得行数不匹配 //当然二进制枚举也可以从1开始枚举 for(int i 0;i n;i) { for(int j 0;j m;j) { cin a[i][j]; } } //ret表示最终的选法 int ret 0; //固定行的选择 for(int st 0;st (1 n);st) { //st里1的个数就表示行的选择 //统计出st里1的个数就表示选择了多少行 //如果选择的行数已经大于k了那这种取法就是不可行的 int cnt calc(st); if(cnt k) { continue; } //sum表示当前选法的总和 int sum 0; int col[N] {0}; //接下来就是将被选择的行的行和累加起来 for(int i 0;i n;i) { for(int j 0;j m;j) { //如果为1就说明该行被选择了 //全部累加到sum里 if((st i) 1) sum a[i][j]; //如果为0就说明该行没选那就没有清零 //就将该行的所有列全部统计到col里 //比如说第i行没有被选则第i行1列~第i行m列的所有数据都不用清零全部统计到col里 //col[j]表示第j列的和 else col[j] a[i][j]; } } //到这选择的所有行的行和已经统计在了sum里 //接下来就贪心的选择列总共选择k-cnt列每列的和已经统计在了col里但是要防止k-cntm的情况 //排降序取前k-cnt列 sort(col, col m, comp); int tcnt min(k - cnt, m); for(int i 0;i tcnt;i) { sum col[i]; } ret max(ret, sum); } cout ret endl; return 0; }P1012 [NOIP 1998 提高组] 拼数 - 洛谷题目的意思就是输出n个数字首尾拼接所能得到最大数字。对于数字a和b我怎么知道谁放在前边谁放在后边呢其实就拼接一下比比大小就知道了如果abba那a就放b前边如果abba那就b放在a前边如果abba谁前谁后无所谓。升华本题其实就是对n个数字进行排序然后依次输出因此这种题目的核心就是找到排序规则是关键。#includeiostream using namespace std; #includealgorithm const int N 25; int n; //题目的数字范围比较大拼接之后会很大因此直接用字符串读入 string s[N]; bool cmp(string s1, string s2) { //只要这个比较为true则s1就放在s2前边 return s1 s2 s2 s1; } int main() { cin n; for(int i 1;i n;i) cin s[i]; sort(s 1, s 1 n, cmp); for(int i 1;i n;i) { cout s[i]; } return 0; }P2878 [USACO07JAN] Protecting the Flowers S - 洛谷简单以题目样例分析了一下题意本题的关键其实就是知道奶牛赶回牛圈的顺序也就是排个序然后计算这里这个排序不像上一道题那么简单所以需要自己去推公式也就是比较规则记住只要推导出只关于i和j有关的不等式就可以作为我们的比较规则。经过推导最终得到的就是排序规则。#includeiostream using namespace std; #includealgorithm const int N 1e5 10; int n; //除了牵牛时间还有每分钟的吃花数 //不要分成两个数组t[N]和d[N]分成两个数组的话就不好排序了 //由于最终输出的是最小吃花朵数因此不用记录每头牛的编号 struct cow { int t; int d; }a[N]; bool cmp(cow c1, cow c2) { return c1.t * c2.d c2.t * c1.d; } int main() { cin n; //输入的时候a[i]就表示第i号牛的t和d for(int i 1;i n;i) cin a[i].t a[i].d; sort(a 1, a 1 n, cmp); //sum表示最终结果 //t表示a数组排完序后第i下标里对应的奶牛的总吃草时间 //第一头被牵的奶牛的总吃草时间为0 long long sum 0, t 0; //排完序后a数组里的就是牵牛顺序 for(int i 1;i n;i) { //a[i]不表示i号奶牛了而是表示被牵走的第i只奶牛 //t就表示被牵走的第i只奶牛的总吃草时间 sum a[i].d * t; //更新下一头奶牛的总吃草时间就等于t加上当前被牵走的奶牛来回总用时 t 2 * a[i].t; } cout sum; return 0; }P1842 [USACO05NOV] 奶牛玩杂技 - 洛谷本题要求的是总压扁指数最小时候的奶牛的顺序这题也是要给奶牛排序也是用上一道题类似的推导方式从而确定奶牛的顺序。#includeiostream using namespace std; #includealgorithm typedef long long LL; const int N 5e4 10; int n; struct cow { int w; int s; }a[N]; bool cmp(cow c1, cow c2) { return max(-c1.s, c1.w-c2.s) max(c2.w-c1.s, -c2.s); } int main() { cin n; for(int i 1;i n;i) cin a[i].w a[i].s; //这里排完序之后得到的顺序就是从上到下的奶牛顺序 //且保证了在此排序下总压扁指数最小 sort(a 1, a 1 n, cmp); //压扁指数算出来有可能是负数 //w表示从上往下第i只奶牛上边所有奶牛的总重 LL ret -1e10, w 0; for(int i 1;i n;i) { ret max(ret, w - a[i].s); w a[i].w; } cout ret endl; return 0; }哈夫曼编码在解决这个问题之前得先来了解一下哈夫曼树是什么。了解了哈夫曼树以及哈夫曼树的构建和它的带权路径长度的计算方式之后还需要学一个哈夫曼编码才可以解决这道题。注这里只关心哈夫曼编码本身其他的一些知识暂时就不管了。知道了以上内容之后就可以去解决本题了。题目已经告诉我们每种字符出现的次数求编码后的字符串的最短长度。下图以题目样例说明。因此题目转化为根据每个字符出现的次数构建出哈夫曼树边构建的过程边计算出哈夫曼树的带权路径长度就是最终结果。注上文已经说了哈夫曼树的形态和哈夫曼编码可能不一样但哈夫曼树的带权路径长度是唯一的所以其实就不存在编码后字符串的长度最短一说。#includeiostream using namespace std; #includequeue #includevector typedef long long LL; int n; //构建哈夫曼树的时候每次要拿权值最小的两个点 //所以可以借助小堆 priority_queueLL, vectorLL, greaterLL p; int main() { cin n; for(int i 1;i n;i) { LL a 0; cin a; p.push(a); } //取堆顶数据两次即获得堆里最小的两个数据作为叶子结点 //ret表示最短路径长度除根节点外的所有结点的权值相加 LL ret 0; while(p.size() 1) { LL x p.top(); p.pop(); LL y p.top(); p.pop(); ret x y; p.push(x y); } cout ret; return 0; }P1090 [NOIP 2004 提高组] 合并果子 - 洛谷本题相当于告诉了我们种子的种类以及每种种子的总数。读完题就知道要求的是哈夫曼树的带权路径长度。#includeiostream using namespace std; #includevector #includequeue typedef long long LL; int n; priority_queueLL, vectorLL, greaterLL p; int main() { cin n; for(int i 1;i n;i) { LL a 0; cin a; p.push(a); } LL ret 0; while(p.size() 1) { LL x p.top(); p.pop(); LL y p.top(); p.pop(); ret x y; p.push(x y); } cout ret; return 0; }P1803 凌乱的yyy / 线段覆盖 - 洛谷本题是典型的区间问题。就是题目给出的对象是一个个区间这种题属于区间问题这一类的。题目的意思就是让我们从题给所有区间中找出不重叠区间的个数最多是多少。如下图题给样例中不相交区间个数最多是2个[0, 2]和[2, 4]。还有一个注意点就是本题的区间的结尾和开头如果相等的话不算区间重合就比如[0, 2]区间的结尾是2[2, 4]区间的开头是2不算做这两个区间重合但并不是每道题都是这样的得就题论题。一般区间问题的第一步就是先对所有区间进行排序一共有四种情况分别是对左端点排升序左端点排降序右端点排升序右端点排降序。具体是哪种排序只能一个个试对于本题来说就直接左端点升序就是最终结果先用这种方式来解决一下问题一个个试的环节就留给下一道题吧。#includeiostream using namespace std; #includealgorithm const int N 1e6 10; int n; struct rage { //分别表示左右端点 int l; int r; }a[N]; //按照左端点排升序 bool cmp(rage g1, rage g2) { return g1.l g2.l; } int main() { cin n; for(int i 1;i n;i) cin a[i].l a[i].r; sort(a 1, a 1 n, cmp); int ret 1; //默认第一个区间为基准则第一个区间被选了ret初始化为1 int r a[1].r; for(int i 2;i n;i) { int left a[i].l; int right a[i].r; //第一个if成立说明两个区间重叠了 //选择右端点较小的那个 if(left r) { //由于一开始ret1了 //这里就只需要更新一下下一次的比较基准区间的右端点即可 r min(r, right); } else { //说明区间没重合 ret; r right; } } cout ret; return 0; }总结UVA1193 Radar Installation - 洛谷#includeiostream using namespace std; #includealgorithm #includecmath const int N 1010; int n; double d;//这里涉及到勾股定理得用浮点数运算 //计算出的区间存在rag结构体里 struct rag { double l; double r; }a[N]; //左端点升序 bool cmp(rag r1, rag r2) { return r1.l r2.l; } int main() { int cnt 0;//标记当前是第几组数据 //由于有多组数据 //本题是按0 0终止的逗号表达式的结果是最后一个表达式 //也就是nd的结果当它为假的时候正好表示n0d0 while(cin n d, n d) { //flag用于判断yd的情况方便下边输出-1 //题目说的是找到雷达总数最小能覆盖所有岛屿这里有一个老鼠屎整组数据都不行了 bool flag false; //计算出区间 for(int i 1;i n;i) { double x 0, y 0; cin x y; //这种情况计算不出来 if(y d) flag true; double len sqrt(d * d - y * y); a[i].l x - len; a[i].r x len; } cout Case cnt :; if(flag) cout -1 endl; else { //排序寻找不重叠的区间组 sort(a 1, a 1 n, cmp); //一开始就拿a[1]这段区间作为基准区间 //最差情况就它这一段区间需要一个雷达因此ret更新为1 int ret 1; double R a[1].r; for(int i 2;i n;i) { double left a[i].l; double right a[i].r; //情况1区间重叠 if(R left) { R min(R, right); } else { ret; R right; } } cout ret endl; } } return 0; }P2887 [USACO07NOV] Sunscreen G - 洛谷#includeiostream using namespace std; #includealgorithm const int N 2510; int C, L; struct s { int x;//对于a数组表示minSPF对于b数组表示第i种防晒霜的SPF int y;//对于a数组表示maxSPF对于a数组表示第i种防晒霜有几瓶 }a[N], b[N];//a和b分别表示奶牛所能承受的SPF范围和防晒霜的SPF以及瓶数 //a和b的排序方式相同 bool cmp(s s1, s s2) { return s1.x s2.x; } int main() { cin C L; for(int i 1;i C;i) cin a[i].x a[i].y; for(int i 1;i L;i) cin b[i].x b[i].y; //a数组按照左端点降序 //b数组按照SPF降序排 sort(a 1, a 1 C, cmp); sort(b 1, b 1 L, cmp); //分发防晒霜 int ret 0; //便利每一段SPF区间 for(int i 1;i C;i) { int left a[i].x; int right a[i].y; //从大到小每一种防晒霜去试直到有合适的 for(int j 1;j L;j) { int SPF b[j].x; //注意这里cnt改变b[j].y也要跟着改因此用引用 int cnt b[j].y; if(cnt 0) continue; if(SPF right) continue; if(SPF left) break;//最大的那瓶都不行说明肯定没有一瓶是行的 //到这说明没有continueSPF的范围是合法的 //SPFleft SPFright //说明该瓶防晒霜可以给第i头奶牛 ret; --cnt; break;//这头奶牛已经有防晒霜了直接break } } cout ret; return 0; }P2859 [USACO06FEB] Stall Reservations S - 洛谷#includeiostream #includequeue #includealgorithm using namespace std; const int N 5e4 10; //c既存线段信息也表示存入堆的信息 struct c { int x;//表示奶牛挤奶开始时间 / 奶牛挤奶结束时间 int y;//表示奶牛挤奶结束时间 / 牛棚编号 int z;//表示奶牛的编号 //堆里按照挤奶结束时间排序 //表示小堆 bool operator(const c c1) const { return x c1.x; } }a[N]; int n; int ret[N];//结果数组 bool cmp(c c1, c c2) { return c1.x c2.x; } int main() { cin n; for(int i 1;i n;i) { cin a[i].x a[i].y; a[i].z i; } //拍完序后数组的下标就不再对应奶牛的题给编号了 //z的作用就是帮我们找到起始编号 sort(a 1, a 1 n, cmp); priority_queuec q; int num 0;//牛棚总数 //先给第一头奶牛分配牛棚 //第一头奶牛肯定要新开一个牛棚 //a[1]表示排完序后左端点最小的那头奶牛a[1].z表示该头奶牛起始的编号 //由于最后要按照起始编号输出结果因此得这么写 ret[a[1].z] 1; q.push({a[1].y, 1}); //1表示牛棚编号 num; for(int i 2;i n;i) { int left a[i].x; int right a[i].y; if(left q.top().x) { //将奶牛安排到q.top()对应得牛棚编号里 c cbackup q.top(); q.pop(); ret[a[i].z] cbackup.y; q.push({a[i].y, cbackup.y}); } else { num; ret[a[i].z] num; q.push({a[i].y, num}); } } cout num endl; for(int i 1;i n;i) { cout ret[i] endl; } return 0; }