免费网站可以做cpa?,网站好坏的指标,档案网站建设存在的问题,手机网站与pc网站的区别报名明年4月蓝桥杯软件赛的同学们#xff0c;如果你是大一零基础#xff0c;目前懵懂中#xff0c;不知该怎么办#xff0c;可以看看本博客系列#xff1a;备赛20周合集 20周的完整安排请点击#xff1a;20周计划 每周发1个博客#xff0c;共20周。 在QQ群上答疑#x…报名明年4月蓝桥杯软件赛的同学们如果你是大一零基础目前懵懂中不知该怎么办可以看看本博客系列备赛20周合集 20周的完整安排请点击20周计划 每周发1个博客共20周。 在QQ群上答疑 文章目录 1. 贪心思想2. 经典贪心问题2.1 部分背包问题2.2 不相交区间问题或称为区间调度问题、活动安排问题2.3 区间合并问题2.4 区间覆盖问题 3. 例题3.1 买二赠一3.2 购物3.3 管道 4. 习题 第9周: 贪心
备赛20周活动已经到第11周了快到期末考试阶段了。最近做题的人很少了。
1. 贪心思想 贪心是蓝桥杯省赛的必考知识点每年都有。 贪心Greedy是容易理解的算法思想把整个问题分解成多个步骤在每个步骤都选取当前步骤的最优方案直到所有步骤结束在每一步都不考虑对后续步骤的影响在后续步骤中也不能回头改变前面的选择
作者拟过2句赠言“贪心说我从不后悔我走过的路”“贪心说其实我有一点后悔但是我回不了头”
大多数读者选前一句。贪心策略在生活中经常用到。例如下象棋时初级水平的棋手只会“走一步看一步”就是贪心法。而水平高的棋手能“走一步看三步”轻松击败初级棋手。 贪心这种“只顾当下不管未来”的解题策略让人疑惑在完成所有局部最优操作后得到的解不一定是全局最优那么热如何判断能不能用贪心呢 有时很容易判断一步一步在局部选择最优最后结束时能达到全局最优。例如吃自助餐怎么吃才能“吃回票价”它的数学模型是一类背包问题称为“部分背包问题”有一个容量为C的背包有m种物品第i种物品有wi千克单价为vi且每种物品是可以分割的例如大米、面粉等问如何选择物品使得装满背包时总价值最大。显然可以用贪心法只要在当前物品中选最贵的放进背包就行了先选最贵的物品AA放完之后再选剩下最贵的物品B…直到背包放满。 有时看起来能用贪心但实际上贪心的结果不是最优解。例如最少硬币支付问题有多种面值的硬币数量不限需要支付M元问怎么支付才能使硬币数量最少 最少硬币支付问题是否能用贪心求最优解和硬币的面值有关。 任意面值的最少硬币支付问题正解是动态规划。参考《算法竞赛入门到进阶》清华大学出版社罗勇军著“7.1.1 硬币问题”给出了各种硬币问题的动态规划解法。 如果硬币面值为1元、2元、5元用贪心是对的。贪心策略是当前选择可用的最大面值的硬币。例如支付M18元第一步选面值最大的5元硬币用掉3个硬币还剩3元第二步选面值第二大的2元硬币用掉1个硬币还剩1元最后选面值最小的1元硬币用掉1个共用5个硬币。在这个解决方案中硬币数量总数是最少的贪心法的结果是全局最优的。 但是如果是其他面值的硬币贪心法就不一定能得到全局最优解。例如硬币的面值很奇怪分别是1、2、4、5、6元。支付M 9元如果用贪心法每次选择当前最大面值硬币那么答案是6 2 1需要3个硬币而最优解是5 4只需要2个硬币。 判断一个题目是不是能用贪心需要满足以下特征 1最优子结构性质。当一个问题的最优解包含其子问题的最优解时称此问题具有最优子结构性质也称此问题满足最优性原理。 2贪心选择性质。问题的整体最优解可以通过一系列局部最优的选择来得到。也就是说通过一步步局部最优能最终能得到全局最优。 最后讨论贪心法的效率贪心法的计算量是多少贪心法由于每一步都在局部做计算且只选取当前最优的步骤做计算不管其他可能的计算方案所以计算量很小。在很多情况下贪心法可以说是计算复杂度最低的算法了。与此相对暴力法一般是计算复杂度最差的因为暴力法计算了全局的所有可能的方案。 由于贪心的效率高所以如果一个问题确定可用贪心法能得到最优解那么应该使用贪心。如果用其他算法大概率会超时。 在算法竞赛中贪心法几乎是必考点有的题考验思维能力有的题结合了贪心和其他算法。虽然贪心策略很容易理解但贪心题可能很难。 贪心也是蓝桥杯大赛的常见题型。不论是省赛还是国赛贪心出现的概率都非常大。 虽然贪心法不一定能得到最优解但是它解题步骤简单、编程容易、计算量小得到的解“虽然不是最好但是还不错”。像蓝桥杯这种赛制一道题有多个测试点用贪心也许能通过10%~30%若别无他法值得一试。
2. 经典贪心问题
2.1 部分背包问题 前文介绍了用贪心求解部分背包问题下面是例题。 例题部分背包问题 下面直接给出代码。 C代码
#includebits/stdc.h
using namespace std;
struct gold{ double w,v,p; }a[105]; //w,v,p: 重量,价值,单价
bool cmp(gold a, gold b){ return a.p b.p; } //单价从大到小排序
int main(){int n,c; cinnc;for(int i0;in;i){cin a[i].w a[i].v;a[i].p a[i].v/a[i].w; //计算单价}sort(a,an,cmp); //按单价排序double sum0.0; //最大价值for(int i0;in;i){if(c a[i].w){ //第i种金币比背包容量小c - a[i].w; //背包还有余量sum a[i].v; //累计价值}else{ //第i种金币很多直接放满背包sum c*a[i].p;break;}}printf(%.2f,sum);//保留小数点后两位输出return 0;
}Java代码
import java.util.*;
class Main {static class Gold { double w, v, p; }public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();int c scanner.nextInt();Gold[] a new Gold[n];for (int i 0; i n; i) {a[i] new Gold();a[i].w scanner.nextDouble();a[i].v scanner.nextDouble();a[i].p a[i].v/a[i].w;}Arrays.sort(a, new ComparatorGold() {public int compare(Gold a, Gold b) {return Double.compare(b.p, a.p);}});double sum 0.0;for (int i 0; i n; i) {if (c a[i].w) {c - a[i].w;sum a[i].v;} else {sum c * a[i].p;break;}}System.out.printf(%.2f, sum);}
}Python代码
n, c map(int, input().split())
a []
for i in range(n):w, v map(int, input().split())p v / wa.append((w, v, p))
a.sort(keylambda x: x[2], reverseTrue)
sum 0.0
for i in range(n):if c a[i][0]:c - a[i][0]sum a[i][1]else:sum c * a[i][2]break
print(%.2f %sum)2.2 不相交区间问题或称为区间调度问题、活动安排问题 给定一些区间活动每个区间有左端点和右端点开始时间和终止时间要求找到最多的不相交区间活动。 以下按“活动安排问题”来解释。 这个问题的目的是求最多活动数量所以那种持续时间长的活动不受欢迎受欢迎的是尽快结束的、持续时间短的活动。 考虑以下3种贪心策略 1按最早开始时间贪心先选最早开始的活动a当a结束后再选下一个最早开始的活动。这种策略不好因为它没有考虑活动的持续时间。假如a一直不结束那么其他活动就不能开始。 2最早结束时间先选最早结束的活动aa结束后再选下一个最早结束的活动。这种策略是合理的。越早结束的活动越能腾出后续时间容纳更多的活动。 3用时最少先选时间最短的活动a再选不冲突的下一个最短活动。这个策略似乎也可行但是很容易找到反例证明这个策略不正确。 下图的例子 用“策略1最早开始时间”选3 用“策略2最早结束时间”选1、2、5、6 用“策略3用时最少”选4、1、2。 策略2的结果是最好的。 总结活动安排问题的贪心策略先按活动的结束时间区间右端点排序然后每次选结束最早的活动并保证选择的活动不重叠。
例题线段覆盖
C代码
#includebits/stdc.h
using namespace std;
struct data{int L, R; //开始时间、结束时间
}a[1000005];
bool cmp(data x,data y){return x.Ry.R; } //按照结束时间排序
int main(){int n; cin n;for(int i0;in;i) cina[i].La[i].R;sort(a,an,cmp);int ans 0;int lastend -1;for(int i0;in;i)if(a[i].Llastend) {ans;lastend a[i].R;}coutans;return 0;
}Java代码
import java.util.*;
class Main {static class Data { int L, R; } // 开始时间、结束时间public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();Data[] a new Data[n];for (int i 0; i n; i) {a[i] new Data();a[i].L scanner.nextInt();a[i].R scanner.nextInt();}Arrays.sort(a, new ComparatorData() {public int compare(Data x, Data y) {return x.R - y.R;}});int ans 0;int lastend -1;for (int i 0; i n; i) if (a[i].L lastend) {ans;lastend a[i].R;}System.out.println(ans);}
}python代码
n int(input())
a []
for _ in range(n):L, R map(int, input().split())a.append((L, R))
a.sort(keylambda x: x[1]) # 按照结束时间排序。请与下一个例题比较
ans 0
lastend -1
for i in range(n):if a[i][0] lastend:ans 1lastend a[i][1]
print(ans)2.3 区间合并问题 区间合并问题给定若干个区间合并所有重叠的区间并返回不重叠的区间个数。 以下图为例1、2、3、5合并4、6合并新区间是1’、4’。 贪心策略按区间左端点排序然后逐一枚举每个区间合并相交的区间。 定义不重叠的区间个数答案为ans。设当前正在合并的区间的最右端点为end枚举到第i个区间[Li, Ri]时 若Li≤end说明与第i区间相交需要合并ans不变更新end max(end, Ri)。 若Li end说明与第i区间不相交ans加1更新 end max(end, Ri)。 请读者用上图的例子模拟合并过程。
2.4 区间覆盖问题 区间覆盖问题给定一个目标大区间和一些小区间问最少选择多少小区间可以覆盖大区间。 贪心策略尽量找出右端点更远的小区间。 操作步骤先对小区间的左端点排序然后依次枚举每个小区间在所有能覆盖当前目标区间右端点的区间之中选择右端点最大的区间。 下图中求最少用几个小区间能覆盖整个区间。先按左端点排序。设当前覆盖到了位置R选择的小区间数量为cnt。 从区间1开始R的值是区间1的右端点ARA。cnt1。 找到能覆盖RA的区间2、3在区间2、3中选右端点更远的3更新R为区间3的右端点BRB。cnt2。 区间4不能覆盖RB跳过。 找到能覆盖RB区间5更新RC。cnt3。结束。
例题区间覆盖
C代码
#includebits/stdc.h
using namespace std;
typedef long long ll;
struct data{ll L,R;
} a[100005];
bool cmp(data x,data y){return x.L y.L; } //按左端点排序
int main(){int n; cinn;for (int i0;in;i) cina[i].La[i].R;sort(a,an,cmp);ll lastend-1,ans0;for (int i0;in;i)if (a[i].R lastend){ans a[i].R - max(lastend,a[i].L)1;lastend a[i].R1;}coutans;return 0;
}Java代码
import java.util.*;class Main {static class Data {long L, R;}public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();Data[] a new Data[n];for (int i 0; i n; i) {a[i] new Data();a[i].L scanner.nextLong();a[i].R scanner.nextLong();}Arrays.sort(a, new ComparatorData() {public int compare(Data x, Data y) {return Long.compare(x.L, y.L);}});long lastend -1;long ans 0;for (int i 0; i n; i) if (a[i].R lastend) {ans a[i].R - Math.max(lastend, a[i].L) 1;lastend a[i].R 1;}System.out.println(ans);}
}python代码
class Data: def __init__(self, L, R):self.L Lself.R R
def cmp(x, y): return x.L y.L #这里用函数比较。请对比上一题代码n int(input())
a []
for _ in range(n):L, R map(int, input().split())a.append(Data(L, R))
a.sort(keylambda x: x.L)
lastend -1
ans 0
for i in range(n):if a[i].R lastend:ans a[i].R - max(lastend, a[i].L) 1lastend a[i].R 1
print(ans)
3. 例题
3.1 买二赠一
2023年蓝桥杯省赛 Java B组 G题 20分 看起来这20分不难拿哦
链接买二赠一 最贵的商品显然不能免单买了2个不能免单的最贵商品后获得一个免单机会那么这个免单机会给谁呢就给能免单的最贵的那个商品。这个贪心思路显然是对的。 以样例为例先排序得{8 7 5 4 2 1 1}。先购买最贵的8、7然后可以免单的最贵的是2。再购买剩下的最贵的5、4免单1。最后单独买1。总价是25。 C代码。需要查找价格为P/2的商品 由于价格已经排序可以用二分法加快查找的时间。这里直接用二分法的库函数lower_bound()查找。
#includebits/stdc.h
using namespace std;
const int N 5e5 10;
int a[N];
bool vis[N]; //vis[i]1表示已经免单了
int main(){int n; scanf(%d, n);for(int i 0; i n; i) scanf(%d, a[i]);sort(a, a n);long long ans 0;int cnt 0;int last -1; //购买的2件中的便宜的那件last_id n-1; //能免单的位置for(int i n-1; i 0; i--){if(!vis[i])cnt, ans a[i], last a[i]; //last是买的第2件if(cnt 2){ //买了2个cnt 0;int x lower_bound(a , a last_id, last / 2) - a; //找能免单的商品a[x]if(x last_id || a[x] last / 2) x--; //向下取整if(x0){vis[x] 1; //x免单了last_id x-1; //后面能免单的区间范围是[0,last_id]}}}coutansendl;return 0;
}Java代码。Java没有自带的二分函数只好自己写一个lowerBound()。
import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();int[] a new int[n];for (int i 0; i n; i) a[i] scanner.nextInt();Arrays.sort(a);long ans 0;int cnt 0;int last -1;int last_id n - 1;boolean[] vis new boolean[n];for (int i n - 1; i 0; i--) {if (!vis[i]) {cnt;ans a[i];last a[i];}if (cnt 2) {cnt 0;int x lowerBound(a, 0, last_id, last / 2);if (x last_id || a[x] last / 2) x--;if (x 0) {vis[x] true;last_id x - 1;}}}System.out.println(ans);}private static int lowerBound(int[] a, int L, int R, int target) {while (L R) {int mid L (R - L) / 2;if (a[mid] target) R mid;else L mid 1;}return L;}
}
Python代码。自带的二分函数是bisect_left()。
import bisect
n int(input())
a list(map(int, input().split()))
a.sort()
ans 0
cnt 0
last -1
last_id n - 1
vis [False] * n
for i in range(n - 1, -1, -1):if not vis[i]:cnt 1ans a[i]last a[i]if cnt 2:cnt 0x bisect.bisect_left(a, last // 2, 0, last_id)if x last_id or a[x] last // 2: x - 1if x 0:vis[x] Truelast_id x - 1
print(ans)3.2 购物
链接购物 为方便处理把硬币面值从小到大排序。 无解是什么情况如果没有面值1的硬币组合不到1无解。如果有面值1的硬币那么所有的X都能满足有解。所以无解的充要条件是没有面值1的硬币。 组合出1~X的任意值需要的硬币多吗学过二进制的人都知道1、2、4、8、…、 2 n − 1 2^{n-1} 2n−1这n个值可以组合出1~ 2 n 2^n 2n-1的所有数。这说明只需要很少的硬币就能组合出很大的X。 设已经组合出1~s的面值即已经得到数字1、2、3、…、s下一步扩展到s1。当然如果能顺便扩展到s2、s3、…扩展得越大越好这样就能用尽量少的硬币扩展出更大的面值。 如何扩展到s1就是在数字1、2、3、…、s的基础上添加一个面值为v的硬币得到s1。v可以选1、2、…、s1例如v1s1svv2s1s-1v…vs1s1v。如果vs2就不能组合到s1了。 v的取值范围是[1, s1]为了最大扩展选v为[1, s1]内的最大硬币此时s扩展到sv。这就是贪心策略。 以本题的输入样例为例说明计算过程。设答案为ans。 先选硬币1得到s1。ans1。 再选[1, s1][1, 2]内的最大硬币2扩展s1为s1v3。ans2。 再选[1, s1][1, 4]内的最大硬币2得到s5。ans3。 再选[1, s1][1, 6]内的最大硬币5得到s10。ans4。 再选[1, s1][1, 11]内的最大硬币10得到s20。ans5。此时s≥X结束。 所以仅需5个面值1、2、2、5、10的硬币就可以组合得到1、2、3、4、…、20。 C/C代码。第11行找[1, s]内的最大面值硬币可以用二分法优化。本题不优化也能通过测试。
#include bits/stdc.h
using namespace std;
int a[105]; //存硬币面值
int main(){int x,n; cin x n;for(int i0;in;i) cin a[i];sort(a,an);if(a[0]!1){ cout-1; return 0;} //无解int s0,ans0;while(sx)for(int vn-1;v0;v--)if(a[v]s1) { //找到[1,s]内的最大面值硬币a[v]sa[v]; //扩展sans;break;}cout ans;
}Java代码
import java.util.Arrays;
import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner input new Scanner(System.in);int x input.nextInt();int n input.nextInt();int[] a new int[n];for (int i 0; i n; i) a[i] input.nextInt(); Arrays.sort(a);if (a[0] ! 1) { System.out.println(-1); return; }int s 0;int ans 0;while (s x) for (int v n - 1; v 0; v--) if (a[v] s 1) {s a[v];ans;break;}System.out.println(ans);}
}python代码
x, n map(int, input().split())
a list(map(int, input().split()))
a.sort()
if a[0] ! 1: print(-1); exit()
s, ans 0, 0
while s x:for v in range(n - 1, -1, -1):if a[v] s 1:s a[v]ans 1break
print(ans)
3.3 管道
2023年蓝桥杯省赛 Python B组 D题 10分 这10分似乎不难拿
链接管道 按题目的设定管道内是贯通的每个阀门都连着一个进水管打开阀门后会有水从这个进水管进入管道并逐渐流到管道内所有地方。 先解释样例。设长度L的单位是米水流的速度是米/秒。 L1处的阀门在第S1秒打开T5秒时覆盖范围L(TS)1-(5-1)-3L(TS)1(5-1)5 L6处的阀门在S5秒打开T5秒时只覆盖了L6 L10处的阀门在L2秒打开T5秒时覆盖范围L(TS)10-(5-2)7L(TS)10(5-2)13。 所以这3个阀门在T5时覆盖了[-3, 5]、6、[713]管道所有传感器都检测到了水流。 读者可能立刻想到可以用二分法猜时间T。先猜一个T然后判断在T时刻是否整个管道有水。如何判断位于Li的阀门它影响到的小区间是[Li(TiSi), Li(TiSi)]n个阀门对应了n个小区间。那么问题转化为给出n个小区间是否能覆盖整个大区间这就是上一节提到的“区间覆盖问题”。 本题还可以再简单一点。题目给的评测用例指出Li-1 Li即已经按左端点排序了可以省去排序的步骤。 C代码。在check((t)函数中定义last_L为当前覆盖到的最左端last_R为最右端。然后逐个遍历所有的小区间看它对扩展last_L、last_R有无贡献。所有小区间处理完毕后如果[last_L、last_R]能覆盖整个[1, len]区间这个时刻t就是可行的。 第32行把二分mid写成mid ((R - L) 1) L而不是mid (R L) 1是因为RL可能溢出。R的最大值是2e9L的最大值是1e9RL超过了int的范围。为什么第30行定义R的初值为2e9请读者思考。 C代码
#includebits/stdc.h
using namespace std;
const int N 1e5 10;
const int LEN 1e9;
int n, len;
int L[N], S[N];
bool check(int t){ // 检查t时刻管道内是否都有水int cnt 0;int last_L 2, last_R 1;for(int i 0; i n; i)if(t S[i]){cnt; //特判t是否够大int left L[i] - (t - S[i]);int right L[i] (t - S[i]);if(left last_L)last_L left, last_R max(last_R, right);else if(left last_R 1)last_R max(last_R, right);}if(cnt 0) return false;if(last_L 1 last_R len)return true;elsereturn false;
}
int main(){scanf(%d%d, n, len);for(int i 0; i n; i)scanf(%d%d, L[i], S[i]);int L 0, R 2e9, ans -1;while(L R){ //二分int mid ((R - L) 1) L; //如果写成(LR)1可能溢出if(check(mid)) ans mid, R mid - 1;else L mid 1;}printf(%d\n, ans);return 0;
}Java代码
import java.util.Scanner;
public class Main {static int[] L;static int[] S;static int n;static int len;public static boolean check(int t) {int cnt 0;int last_L 2;int last_R 1;for(int i 0; i n; i) {if(t S[i]) {cnt;int left L[i] - (t - S[i]);int right L[i] (t - S[i]);if(left last_L) {last_L left;last_R Math.max(last_R, right);} else if(left last_R 1) {last_R Math.max(last_R, right);}}}if(cnt 0) return false;if(last_L 1 last_R len) return true;else return false;}public static void main(String[] args) {Scanner scanner new Scanner(System.in);n scanner.nextInt();len scanner.nextInt();L new int[n];S new int[n];for(int i 0; i n; i) {L[i] scanner.nextInt();S[i] scanner.nextInt();}int L 0;int R 2000000000;int ans -1;while(L R) {int mid ((R - L) 1) L;if(check(mid)) {ans mid;R mid - 1;} else L mid 1; }System.out.println(ans);}
}python代码
def check(t):cnt 0last_L 2last_R 1for i in range(n):if t S[i]:cnt 1left L[i] - (t - S[i])right L[i] (t - S[i])if left last_L:last_L leftlast_R max(last_R, right)elif left last_R 1:last_R max(last_R, right)if cnt 0: return Falseif last_L 1 and last_R length: return Trueelse: return Falsen, length map(int, input().split())
L []
S []
for _ in range(n):l, s map(int, input().split())L.append(l)S.append(s)
L_val,R_val 0, int(2e9)
ans -1
while L_val R_val:mid (R_val L_val) 1if check(mid):ans midR_val mid - 1else: L_val mid 1
print(ans)
4. 习题
答疑 https://www.lanqiao.cn/problems/1025/learning/ 身份证 https://www.lanqiao.cn/problems/3849/learning/ 翻硬币 https://www.lanqiao.cn/problems/209/learning/ 防御力 https://www.lanqiao.cn/problems/226/learning/ 合并果子 https://www.luogu.com.cn/problem/P1090 排队接水 https://www.luogu.com.cn/problem/P1223 小A的糖果 https://www.luogu.com.cn/problem/P3817 负载平衡问题 https://www.luogu.com.cn/problem/P4016 找零钱 https://www.lanqiao.cn/problems/3854 01搬砖 https://www.lanqiao.cn/problems/2201/learning/ 卡牌游戏 https://www.lanqiao.cn/problems/1057/learning 寻找和谐音符 https://www.lanqiao.cn/problems/3975/learning 三国游戏 https://www.lanqiao.cn/problems/3518/learning/ 平均 https://www.lanqiao.cn/problems/3532/learning/ 小蓝的旅行计划 https://www.lanqiao.cn/problems/3534/learning/ 排座椅 https://www.luogu.com.cn/problem/P1056 母舰 https://www.luogu.com.cn/problem/P2813 加工生产调度 https://www.luogu.com.cn/problem/P1248
