企业官网建设流程全解析

本文分享的必刷题目是从蓝桥云课、洛谷、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'_i+a_jci′​+aj​。需要注意的是a j a_jaj​可能是正数、0或负数，这意味着小杨参加战斗后对武器的熟练度可能会提高，也可能会不变，还有可能降低。

小杨想请你编写程序帮助他计算出如何选择武器才能使得m mm场战斗后，自已对n nn种武器的熟练度的最大值尽可能大。

【输入】

第一行包含两个正整数n nn，m 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

【核心思想】

1. 问题分析：给定n nn种武器的初始熟练度c i c_ici​和m mm场战斗的熟练度变化值a j a_jaj​。每场战斗必须选择一种武器，该武器熟练度增加a j a_jaj​。求m mm场战斗后所有武器熟练度最大值的最大可能值。这是一个贪心策略问题，核心在于分析如何将每场战斗的增益分配给最优武器。

2. 算法选择：

   • 贪心分配：将最大初始熟练度的武器作为"主武器"，所有正增益都分配给该武器；负增益分配给非主武器（或当只有1 11种武器时不得不承受）
   • 最大值维护：只需追踪当前最大熟练度，无需维护所有武器状态

3. 关键步骤：

   • 读入数据：读取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_{i=1}^{n} c_imx←maxi=1n​ci​，即初始最大熟练度
   • 处理每场战斗（j jj从1 11到m mm）：
     • 若n = 1 n = 1n=1（只有一把武器）：m x ← m x + a j mx \leftarrow mx + a_jmx←mx+aj​（所有变化都作用于该武器）
     • 否则若a j > 0 a_j > 0aj​>0：m x ← m x + a j mx \leftarrow mx + a_jmx←mx+aj​（正增益分配给当前最强武器，使其更强）
     • 否则：不操作（负增益分配给非主武器，不影响最大值）
   • 输出结果：m x mxmx

4. 时间/空间复杂度：

   • 时间复杂度：O ( n + m ) O(n + m)O(n+m)，遍历初始熟练度和战斗增益各一次
   • 空间复杂度：O ( n + m ) O(n + m)O(n+m)，存储输入数组

5. 贪心策略的核心思想：

   • 集中优势资源：所有正增益都集中分配给当前熟练度最高的武器，使其始终保持最大，这是最大化最终最大值的贪心策略
   • 负增益的规避：当有多种武器时，负增益可以分配给非主武器，不影响最大熟练度。只有一把武器时无法规避，必须承受
   • 最优子结构：每场战斗的最优决策只依赖于当前最大熟练度，与具体是哪把武器无关，因此只需维护最大值
   • 单调性保证：正增益使最大值增加，负增益不减少最大值（当n ≥ 2 n \geq 2n≥2时），因此最终最大值具有单调不减性
   • 适用于资源集中分配、最大化极值类贪心问题

【算法标签】

#普及- #贪心

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=100010;// 定义数组大小常量inta[N],c[N];// 定义两个数组，一个存储每场战斗的增益值，一个存储初始熟练度intmain(){intn,m;// 定义变量n和m，分别表示武器种类数和战斗次数cin>>n>>m;// 输入n和mintmx=-10000;// 初始化最大熟练度为一个较小的值for(inti=1;i<=n;i++){// 循环输入每种武器的初始熟练度cin>>c[i];mx=max(mx,c[i]);// 更新当前最大熟练度}for(inti=1;i<=m;i++){// 循环输入每场战斗的增益值cin>>a[i];}for(inti=1;i<=m;i++){// 根据战斗增益更新最大熟练度if(n==1||a[i]>0){// 如果只有一种武器或者当前战斗增益为正mx+=a[i];// 增加最大熟练度}}cout<<mx<<endl;// 输出最终的最大熟练度return0;}

【运行结果】

2 2 9 9 1 -1 10