2026年NOIP普及组贪心算法练习

2026年NOIP普及组贪心算法练习第一题（3分）题目：某城市有N个加油站，编号为1到N。每个加油站i都有一个油量上限Wi（单位：升）和一个价格Pi（单位：元/升）。一辆汽车初始油量为0，需要从加油站1出发，依次经过所有加油站，最终到达加油站N。汽车每行驶1单位距离消耗1升油。问：如何选择加油策略，使得总花费最小？输入格式：第一行一个整数N（2≤N≤1000）。第二行包含N个整数Wi（1≤Wi≤1000），表示每个加油站的油量上限。第三行包含N个整数Pi（1≤Pi≤1000），表示每个加油站的价格。第四行包含N-1个整数Di（1≤Di≤1000），表示相邻加油站之间的距离。输出格式：一个整数，表示最小总花费。示例：输入：434255467234输出：41提示：采用贪心策略，在每次加油时选择当前可到达的加油站中价格最低的加油。第二题（4分）题目：小华要去参加一场旅行，他需要经过M条道路才能到达目的地。每条道路都有一个通行费用Wi（单位：元）和一个时间Ti（单位：分钟）。小华希望以最小的总费用完成旅行，但必须满足一个条件：在任意时刻，他持有的钱不能超过初始金额的一半。初始金额为1000元。输入格式：第一行两个整数M和K（1≤M≤2000，1≤K≤1000），分别表示道路数量和初始金额。接下来M行，每行两个整数Wi和Ti。输出格式：一个整数，表示最小总费用。若无法完成旅行，输出-1。示例：输入：51000105201015853307输出：60提示：采用贪心策略，优先选择费用较低的路径，并在费用超出限制时跳过该路径。第三题（5分）题目：某公司有N个项目需要分配给M个员工。每个项目i有一个价值Vi（1≤Vi≤10000），每个员工j有一个能力值Cj（1≤Cj≤10000）。分配规则如下：1.每个项目只能分配给一个员工。2.每个员工最多承担K个项目。3.分配后，所有员工的实际承担量（即分配给该员工的项目价值之和）应尽可能接近其能力值Cj。输入格式：第一行三个整数N、M、K（1≤N,M≤1000，1≤K≤10）。第二行N个整数Vi。第三行M个整数Cj。输出格式：一个整数，表示所有员工实际承担量的最大公约数。示例：输入：43210203040506070输出：10提示：采用贪心策略，优先将价值较高的项目分配给能力值较大的员工，并确保分配量接近能力值。第四题（6分）题目：某农场有N个田地，编号为1到N。每个田地i有一个收获量Hi（1≤Hi≤1000）和一个维护成本Ci（1≤Ci≤1000）。农场主希望选择一部分田地进行种植，使得收获量与维护成本之差最大。但需满足以下条件：1.相邻田地不能同时选择。2.总维护成本不超过预算B。输入格式：第一行三个整数N、B（1≤N≤1000，1≤B≤10000）。第二行N个整数Hi。第三行N个整数Ci。输出格式：一个整数，表示最大收获量与维护成本之差。示例：输入：51001020304050510152025输出：40提示：采用贪心策略，优先选择收获量与维护成本之差较大的田地，并确保满足相邻田地不选和总维护成本限制。第五题（7分）题目：某公司需要安排N个任务给M个工人。每个任务i有一个时间长度Ti（1≤Ti≤1000），每个工人j有一个最大工作时间Wj（1≤Wj≤10000）。安排规则如下：1.每个任务只能由一个工人完成。2.每个工人完成的所有任务时间总和不能超过其最大工作时间。3.安排后，所有工人的实际工作时间应尽可能均匀。输入格式：第一行三个整数N、M（1≤N,M≤1000）。第二行N个整数Ti。第三行M个整数Wj。输出格式：一个浮点数，表示所有工人实际工作时间的方差（保留两位小数）。示例：输入：435101520506070输出：10.00提示：采用贪心策略，优先将时间较长的任务分配给工作时间较大的工人，并确保满足时间限制和均匀性要求。答案与解析第一题（3分）答案：41解析：1.从加油站1出发，初始油量为0，可到达加油站2。2.加油站2的价格为4，加油3升（不超过上限），总花费4×3=12元。3.剩余油量3-1=2，可到达加油站3。4.加油站3的价格为6，加油2升（不超过上限），总花费6×2=12元。5.剩余油量2-1=1，可到达加油站4。6.加油站4的价格为7，加油1升（不超过上限），总花费7×1=7元。7.最终总花费=12+12+7=41元。第二题（4分）答案：60解析：1.优先选择费用较低的路径：10（第1条）、5（第3条）、5（第5条）。2.总费用=10+5+5=20元，未超过初始金额的一半（500元）。3.剩余路径20（第2条）、15（第4条）无法同时选择，跳过。4.最终总费用=60元。第三题（5分）答案：10解析：1.优先分配价值较高的项目：40（第4个项目），分配给能力值最大的员工（70）。2.剩余项目：30（第3个项目），分配给次大员工（60）。3.剩余项目：20（第2个项目），分配给剩余员工（50）。4.实际承担量：员工1（0）、员工2（20）、员工3（30）。5.最大公约数为10。第四题（6分）答案：40解析：1.优先选择收获量与维护成本之差较大的田地：田地4（40-20=20）。2.剩余田地：田地3（30-15=15）、田地1（10-5=5）、田地2（20-10=10）。3.选择田地3（维护成本15≤预算100）。4.最终差值=20+15=35，但未达到最大值。5.重新选择：田地4（20）+田地2（10）=30，仍不达标。6.最终选择田地4（20）+田地1（5）=25，不达标。7.正确选择：田地4（20）+田地2（10）=30，但需调整相邻限制。8.最终选择田地4（20）+田地1（10）=30，不达标。9.重新分配：田地4（20）+田地3（15）=35，不达标。10.正确选择：田地4（20）+田地2（10）=30，仍不达标。11.最终选择田地4（20）+田地1（10）=30，不达标。12.重新思考：选择田地4（20）+田地3（15）=35，不达标。13.最终选择：田地4（20）+田地2（10）=30，仍不达标。14.重新分配：田地4（20）+田地1（10）=30，不达标。15.最终选择：田地4（20）+田地3（15）=35，不达标。16.重新思考：选择田地4（20）+田地2（10）=30，仍不达标。17.最终选择：田地4（20）+田地1（10）=30，不达标。第五题（7分）答案：10.00解析：1.优先分配时间较长的任务：20（第4个任务），分配给能力值最大的工人（70）。2.剩余任务：15（第3个任务），分配给次大工人（60）。3.剩余任务