![题解：洛谷 B4051 [GESP202409 五级] 小杨的武器](http://pic.xiahunao.cn/yaotu/题解：洛谷 B4051 [GESP202409 五级] 小杨的武器)
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷B4051 [GESP202409 五级] 小杨的武器 - 洛谷【题目描述】小杨有n nn种不同的武器他对第i ii种武器的初始熟练度为c i c_ici。小杨会依次参加m mm场战斗每场战斗小杨只能且必须选择一种武器使用。假设小杨使用了第i ii种武器参加了第j jj场战斗战斗前该武器的熟练度为c i ′ c_ici′则战斗后小杨对该武器的熟练度会变为c i ′ a j c_ia_jci′aj。需要注意的是a j a_jaj可能是正数、0或负数这意味着小杨参加战斗后对武器的熟练度可能会提高也可能会不变还有可能降低。小杨想请你编写程序帮助他计算出如何选择武器才能使得m mm场战斗后自已对n nn种武器的熟练度的最大值尽可能大。【输入】第一行包含两个正整数n nnm mm含义如题面所示。第二行包含n nn个正整数c 1 , c 2 , … , c n c_1,c_2,\dots,c_nc1,c2,…,cn代表小杨对武器的初始熟练度。第三行包含m mm个正整数a , a 2 , … , a m a_,a_2,\dots, a_ma,a2,…,am代表每场战斗后武器熟练度的变化值。【输出】输出一个整数代表m mm场场战斗后小杨对n nn种武器的熟练度的最大值最大是多少。【输入样例】2 2 9 9 1 -1【输出样例】10【核心思想】问题分析给定n nn种武器的初始熟练度c i c_ici和m mm场战斗的熟练度变化值a j a_jaj。每场战斗必须选择一种武器该武器熟练度增加a j a_jaj。求m mm场战斗后所有武器熟练度最大值的最大可能值。这是一个贪心策略问题核心在于分析如何将每场战斗的增益分配给最优武器。算法选择贪心分配将最大初始熟练度的武器作为主武器所有正增益都分配给该武器负增益分配给非主武器或当只有1 11种武器时不得不承受最大值维护只需追踪当前最大熟练度无需维护所有武器状态关键步骤读入数据读取n , m n, mn,m初始熟练度c [ 1.. n ] c[1..n]c[1..n]战斗增益a [ 1.. m ] a[1..m]a[1..m]确定主武器m x ← max i 1 n c i mx \leftarrow \max_{i1}^{n} c_imx←maxi1nci即初始最大熟练度处理每场战斗j jj从1 11到m mm若n 1 n 1n1只有一把武器m x ← m x a j mx \leftarrow mx a_jmx←mxaj所有变化都作用于该武器否则若a j 0 a_j 0aj0m x ← m x a j mx \leftarrow mx a_jmx←mxaj正增益分配给当前最强武器使其更强否则不操作负增益分配给非主武器不影响最大值输出结果m x mxmx时间/空间复杂度时间复杂度O ( n m ) O(n m)O(nm)遍历初始熟练度和战斗增益各一次空间复杂度O ( n m ) O(n m)O(nm)存储输入数组贪心策略的核心思想集中优势资源所有正增益都集中分配给当前熟练度最高的武器使其始终保持最大这是最大化最终最大值的贪心策略负增益的规避当有多种武器时负增益可以分配给非主武器不影响最大熟练度。只有一把武器时无法规避必须承受最优子结构每场战斗的最优决策只依赖于当前最大熟练度与具体是哪把武器无关因此只需维护最大值单调性保证正增益使最大值增加负增益不减少最大值当n ≥ 2 n \geq 2n≥2时因此最终最大值具有单调不减性适用于资源集中分配、最大化极值类贪心问题【算法标签】#普及- #贪心【代码详解】#includebits/stdc.husingnamespacestd;constintN100010;// 定义数组大小常量inta[N],c[N];// 定义两个数组一个存储每场战斗的增益值一个存储初始熟练度intmain(){intn,m;// 定义变量n和m分别表示武器种类数和战斗次数cinnm;// 输入n和mintmx-10000;// 初始化最大熟练度为一个较小的值for(inti1;in;i){// 循环输入每种武器的初始熟练度cinc[i];mxmax(mx,c[i]);// 更新当前最大熟练度}for(inti1;im;i){// 循环输入每场战斗的增益值cina[i];}for(inti1;im;i){// 根据战斗增益更新最大熟练度if(n1||a[i]0){// 如果只有一种武器或者当前战斗增益为正mxa[i];// 增加最大熟练度}}coutmxendl;// 输出最终的最大熟练度return0;}【运行结果】2 2 9 9 1 -1 10
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷B4051 [GESP202409 五级] 小杨的武器 - 洛谷【题目描述】小杨有n nn种不同的武器他对第i ii种武器的初始熟练度为c i c_ici。小杨会依次参加m mm场战斗每场战斗小杨只能且必须选择一种武器使用。假设小杨使用了第i ii种武器参加了第j jj场战斗战斗前该武器的熟练度为c i ′ c_ici′则战斗后小杨对该武器的熟练度会变为c i ′ a j c_ia_jci′aj。需要注意的是a j a_jaj可能是正数、0或负数这意味着小杨参加战斗后对武器的熟练度可能会提高也可能会不变还有可能降低。小杨想请你编写程序帮助他计算出如何选择武器才能使得m mm场战斗后自已对n nn种武器的熟练度的最大值尽可能大。【输入】第一行包含两个正整数n nnm mm含义如题面所示。第二行包含n nn个正整数c 1 , c 2 , … , c n c_1,c_2,\dots,c_nc1,c2,…,cn代表小杨对武器的初始熟练度。第三行包含m mm个正整数a , a 2 , … , a m a_,a_2,\dots, a_ma,a2,…,am代表每场战斗后武器熟练度的变化值。【输出】输出一个整数代表m mm场场战斗后小杨对n nn种武器的熟练度的最大值最大是多少。【输入样例】2 2 9 9 1 -1【输出样例】10【核心思想】问题分析给定n nn种武器的初始熟练度c i c_ici和m mm场战斗的熟练度变化值a j a_jaj。每场战斗必须选择一种武器该武器熟练度增加a j a_jaj。求m mm场战斗后所有武器熟练度最大值的最大可能值。这是一个贪心策略问题核心在于分析如何将每场战斗的增益分配给最优武器。算法选择贪心分配将最大初始熟练度的武器作为主武器所有正增益都分配给该武器负增益分配给非主武器或当只有1 11种武器时不得不承受最大值维护只需追踪当前最大熟练度无需维护所有武器状态关键步骤读入数据读取n , m n, mn,m初始熟练度c [ 1.. n ] c[1..n]c[1..n]战斗增益a [ 1.. m ] a[1..m]a[1..m]确定主武器m x ← max i 1 n c i mx \leftarrow \max_{i1}^{n} c_imx←maxi1nci即初始最大熟练度处理每场战斗j jj从1 11到m mm若n 1 n 1n1只有一把武器m x ← m x a j mx \leftarrow mx a_jmx←mxaj所有变化都作用于该武器否则若a j 0 a_j 0aj0m x ← m x a j mx \leftarrow mx a_jmx←mxaj正增益分配给当前最强武器使其更强否则不操作负增益分配给非主武器不影响最大值输出结果m x mxmx时间/空间复杂度时间复杂度O ( n m ) O(n m)O(nm)遍历初始熟练度和战斗增益各一次空间复杂度O ( n m ) O(n m)O(nm)存储输入数组贪心策略的核心思想集中优势资源所有正增益都集中分配给当前熟练度最高的武器使其始终保持最大这是最大化最终最大值的贪心策略负增益的规避当有多种武器时负增益可以分配给非主武器不影响最大熟练度。只有一把武器时无法规避必须承受最优子结构每场战斗的最优决策只依赖于当前最大熟练度与具体是哪把武器无关因此只需维护最大值单调性保证正增益使最大值增加负增益不减少最大值当n ≥ 2 n \geq 2n≥2时因此最终最大值具有单调不减性适用于资源集中分配、最大化极值类贪心问题【算法标签】#普及- #贪心【代码详解】#includebits/stdc.husingnamespacestd;constintN100010;// 定义数组大小常量inta[N],c[N];// 定义两个数组一个存储每场战斗的增益值一个存储初始熟练度intmain(){intn,m;// 定义变量n和m分别表示武器种类数和战斗次数cinnm;// 输入n和mintmx-10000;// 初始化最大熟练度为一个较小的值for(inti1;in;i){// 循环输入每种武器的初始熟练度cinc[i];mxmax(mx,c[i]);// 更新当前最大熟练度}for(inti1;im;i){// 循环输入每场战斗的增益值cina[i];}for(inti1;im;i){// 根据战斗增益更新最大熟练度if(n1||a[i]0){// 如果只有一种武器或者当前战斗增益为正mxa[i];// 增加最大熟练度}}coutmxendl;// 输出最终的最大熟练度return0;}【运行结果】2 2 9 9 1 -1 10
