本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】瑞学堂瑞瑞的能源网络【题目描述】瑞瑞正在为一座未来城市设计能源分配网络。城市可以看作一个包含n nn个节点的树状结构节点编号为1 11到n nn其中1 11号节点是总能源站。城市中的每条边都代表一条能源管道管道会因材质和长度不同而产生不同的能量损耗。具体来说对于树上的每条边( u , v ) (u,v)(u,v)如果能量从u uu传输到v vv都会有一个对应的损耗值。损耗值是双向不对称的即从u uu到v vv的损耗为w u , v w_{u,v}wu,v而从v vv到u uu的损耗为w v , u w_{v,u}wv,u。城市中的m mm个关键部门分布在一些节点上每个部门都有一个固定的能量需求d i d_idi。瑞瑞希望从总能源站节点1 11出发为一些部门输送能量。由于输送技术限制他每次只能选择一个部门携带一定能量从节点1 11沿简单路径前往该部门所在节点满足其需求后沿原路返回节点1 11这称为一次运输。各次运输之间相互独立但总能量E EE是所有运输消耗的总和。在一次运输中当他到达目标部门所在节点时所携带的剩余能量必须至少等于该部门的需求d i d_idi此时才能成功满足需求注意能量不会被需求消耗仅作为阈值判断。每次运输的能量消耗等于路径上各边损耗之和即去程消耗从1 11到目标节点方向的总损耗回程消耗从目标节点回到1 11方向的总损耗。运输过程中每次运输结束后未消耗的能量会自动回收至总能量池可供后续运输使用。因此在初始拥有总能量E EE的条件下瑞瑞可以任意安排运输顺序。对于第i ii个部门所在的节点设从1 11到该节点的去程损耗为g o i go_igoi回程损耗为b a c k i back_ibacki。一次运输可行当且仅当在执行该运输时剩余能量≥ g o i m a x ( b a c k i , d i ) ≥go_imax(back_i,d_i)≥goimax(backi,di)且该次运输累计消耗g o i b a c k i go_iback_igoibacki。请你帮助瑞瑞计算在总消耗不超过E EE的前提下他最多能成功满足多少个部门的需求。【输入】第一行包含三个整数n , m , E n,m,En,m,E分别表示城市节点数、关键部门数以及初始能量值。接下来n − 1 n−1n−1行每行包含四个整数u , v , w 1 , w 2 u,v,w_1,w_2u,v,w1,w2表示节点u uu和v vv之间有一条管道从u uu到v vv的损耗为w 1 w_1w1从v vv到u uu的损耗为w 2 w_2w2。接下来m mm行每行包含两个整数p i , d i p_i,d_ipi,di表示第i ii个关键部门所在的节点编号以及其能量需求。部门可能位于同一个节点上。【输出】输出一个整数表示在初始能量为E EE且必须返回节点1 11的前提下最多能满足的部门数量。【输入样例】3 2 14 1 2 1 1 1 3 2 6 2 8 3 10【输出样例】2【核心思想】问题分析给定一棵n nn个节点的树1 11为根每条边有双向不对称损耗w u , v w_{u,v}wu,v和w v , u w_{v,u}wv,u。m mm个部门分布在节点上各有需求d i d_idi。每次运输从1 11出发到某部门再返回消耗往返损耗之和。运输可行当且仅当执行时剩余能量≥ g o i max ( b a c k i , d i ) \geq go_i \max(back_i, d_i)≥goimax(backi,di)g o i go_igoi为去程损耗b a c k i back_ibacki为回程损耗。求总消耗不超过初始能量E EE时最多能满足的部门数量。这是一个反悔贪心问题关键在于按门槛排序后用堆维护已选任务实现用更优任务替换已选劣任务的贪心策略。算法选择DFS 预处理计算从节点1 11到每个节点的去程损耗g o i go_igoi和回程损耗b a c k i back_ibacki任务参数化对每个部门计算require go_i max(back_i, d_i)最低能量门槛和cost go_i back_i实际消耗反悔贪心 大根堆按require升序遍历任务能执行则执行并入堆不能执行则尝试用当前任务替换堆中cost最大的已选任务若替换后更优关键步骤建图与 DFS读入n , m , E n, m, En,m,E和n − 1 n-1n−1条边用邻接表存储双向不对称边从节点1 11DFS 计算所有节点的g o gogo和b a c k backback生成任务列表对每个部门若require E则加入tasks过滤不可行任务排序按require升序排序任务反悔贪心遍历若cur t.requirecur - t.cost将t.cost入堆否则若堆非空且pq.top() t.cost若cur pq.top() t.require则弹出堆顶cur cur pq.top() - t.cost将t.cost入堆输出堆的大小时间/空间复杂度时间复杂度O ( n m log m ) O(n m \log m)O(nmlogm)DFSO ( n ) O(n)O(n)排序O ( m log m ) O(m \log m)O(mlogm)堆操作O ( m log m ) O(m \log m)O(mlogm)空间复杂度O ( n m ) O(n m)O(nm)邻接表、任务列表、堆反悔贪心的核心思想门槛优先的贪心基线按require升序处理保证当前能量能执行的任务一定被考虑这是尽可能多完成任务的基础实际消耗的资源竞争总能量有限完成任务数最大化等价于在门槛约束下最小化总消耗堆维护替换候选大根堆存储已选任务的cost堆顶是消耗最大的任务。当遇到新任务无法执行时若其cost小于堆顶替换可减少总消耗可能释放足够能量执行更多任务延迟替换的正确性不立即替换所有可能情况而是在遍历过程中动态调整保证最终堆中任务是门槛约束下的最小消耗组合适用于在满足门槛约束的前提下用有限资源最大化任务数量的问题核心在于将任务量化为门槛消耗二元组通过排序和堆实现动态最优替换【算法标签】#反悔贪心【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglong// 将int定义为long long避免能量计算溢出constintN100005;// 定义数组最大容量为100005intn,m,E;// n为节点数m为部门数E为初始总能量structEdge{intv,go,back;// v为邻接节点go为从u到v的损耗back为从v到u的损耗};vectorEdgeadj[N];// adj[u]存储节点u的所有邻接边双向不对称损耗intgo[N],back[N];// go[i]为从节点1到i的去程总损耗back[i]为从i回到1的回程总损耗// 定义任务结构体每个部门运输所需的能量门槛和实际消耗structTask{intrequire,cost;// require为执行该运输所需的最低能量门槛cost为该运输的实际能量消耗};vectorTasktasks;// 存储所有可行的部门运输任务priority_queueintpq;// 大根堆存储已选任务的实际消耗用于后续替换优化// 深度优先搜索计算从节点1到每个节点的去程和回程总损耗voiddfs(intu,intfa){for(autox:adj[u])// 遍历u的所有邻接边{intvx.v,w1x.go,w2x.back;// v为邻接节点w1为u-v损耗w2为v-u损耗if(vfa)// 跳过父节点避免回溯continue;go[v]go[u]w1;// 累加去程损耗从1到v 从1到u u到vback[v]back[u]w2;// 累加回程损耗从v到1 从u到1 v到udfs(v,u);// 递归遍历子节点}}// 自定义排序按运输所需能量门槛升序排列贪心优先满足门槛低的部门boolcmp(Task x,Task y){returnx.requirey.require;}signedmain()// 使用signed main配合#define int long long{cinnmE;// 读入节点数、部门数、初始能量for(inti1;in;i)// 读入n-1条边的信息{intu,v,w1,w2;cinuvw1w2;adj[u].push_back({v,w1,w2});// u-v损耗w1v-u损耗w2adj[v].push_back({u,w2,w1});// v-u损耗w2u-v损耗w1}go[1]back[1]0;// 节点1为起点去程和回程损耗均为0dfs(1,0);// 从节点1开始DFS计算所有节点的go和back// 处理每个部门计算其运输任务参数for(inti1;im;i){intp,d;// p为部门所在节点d为部门能量需求cinpd;intgo_costgo[p];// 去程损耗intback_costback[p];// 回程损耗// 执行该运输的最低能量门槛去程损耗 max(回程损耗, 部门需求)// 因为到达时剩余能量必须≥需求d且还要能返回所以需要max(back, d)intrequirego_costmax(back_cost,(int)d);// 该运输的实际总消耗去程损耗 回程损耗能量只是门槛判断实际消耗是往返总和intcostgo_costback_cost;// 如果初始能量E足够满足该部门的最低门槛则该任务可行if(requireE)tasks.push_back({require,cost});// 加入可行任务列表}sort(tasks.begin(),tasks.end(),cmp);// 按门槛升序排序// 贪心堆优化尽可能多地满足部门需求intcurE;// cur记录当前剩余能量for(autot:tasks)// 按门槛从低到高遍历每个可行任务{if(curt.require)// 如果当前剩余能量足够执行该运输{cur-t.cost;// 扣除该运输的实际消耗pq.push(t.cost);// 将该任务的消耗加入大根堆}// 如果当前能量不足以执行新任务但可以用更省能量的任务替换已选任务elseif(!pq.empty()pq.top()t.cost)// 如果堆顶已选最大消耗大于当前任务消耗{inttmppq.top();// 取出堆顶消耗最大的已选任务// 如果替换后能量足够执行当前任务if(curtmpt.require){pq.pop();// 移除堆顶任务curcurtmp-t.cost;// 回收堆顶消耗扣除当前消耗更新剩余能量pq.push(t.cost);// 将当前任务加入堆}}}coutpq.size()endl;// 输出堆的大小即最多能满足的部门数量return0;}【运行结果】3 2 14 1 2 1 1 1 3 2 6 2 8 3 10 2 题解：瑞学堂 瑞瑞的能源网络
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】瑞学堂瑞瑞的能源网络【题目描述】瑞瑞正在为一座未来城市设计能源分配网络。城市可以看作一个包含n nn个节点的树状结构节点编号为1 11到n nn其中1 11号节点是总能源站。城市中的每条边都代表一条能源管道管道会因材质和长度不同而产生不同的能量损耗。具体来说对于树上的每条边( u , v ) (u,v)(u,v)如果能量从u uu传输到v vv都会有一个对应的损耗值。损耗值是双向不对称的即从u uu到v vv的损耗为w u , v w_{u,v}wu,v而从v vv到u uu的损耗为w v , u w_{v,u}wv,u。城市中的m mm个关键部门分布在一些节点上每个部门都有一个固定的能量需求d i d_idi。瑞瑞希望从总能源站节点1 11出发为一些部门输送能量。由于输送技术限制他每次只能选择一个部门携带一定能量从节点1 11沿简单路径前往该部门所在节点满足其需求后沿原路返回节点1 11这称为一次运输。各次运输之间相互独立但总能量E EE是所有运输消耗的总和。在一次运输中当他到达目标部门所在节点时所携带的剩余能量必须至少等于该部门的需求d i d_idi此时才能成功满足需求注意能量不会被需求消耗仅作为阈值判断。每次运输的能量消耗等于路径上各边损耗之和即去程消耗从1 11到目标节点方向的总损耗回程消耗从目标节点回到1 11方向的总损耗。运输过程中每次运输结束后未消耗的能量会自动回收至总能量池可供后续运输使用。因此在初始拥有总能量E EE的条件下瑞瑞可以任意安排运输顺序。对于第i ii个部门所在的节点设从1 11到该节点的去程损耗为g o i go_igoi回程损耗为b a c k i back_ibacki。一次运输可行当且仅当在执行该运输时剩余能量≥ g o i m a x ( b a c k i , d i ) ≥go_imax(back_i,d_i)≥goimax(backi,di)且该次运输累计消耗g o i b a c k i go_iback_igoibacki。请你帮助瑞瑞计算在总消耗不超过E EE的前提下他最多能成功满足多少个部门的需求。【输入】第一行包含三个整数n , m , E n,m,En,m,E分别表示城市节点数、关键部门数以及初始能量值。接下来n − 1 n−1n−1行每行包含四个整数u , v , w 1 , w 2 u,v,w_1,w_2u,v,w1,w2表示节点u uu和v vv之间有一条管道从u uu到v vv的损耗为w 1 w_1w1从v vv到u uu的损耗为w 2 w_2w2。接下来m mm行每行包含两个整数p i , d i p_i,d_ipi,di表示第i ii个关键部门所在的节点编号以及其能量需求。部门可能位于同一个节点上。【输出】输出一个整数表示在初始能量为E EE且必须返回节点1 11的前提下最多能满足的部门数量。【输入样例】3 2 14 1 2 1 1 1 3 2 6 2 8 3 10【输出样例】2【核心思想】问题分析给定一棵n nn个节点的树1 11为根每条边有双向不对称损耗w u , v w_{u,v}wu,v和w v , u w_{v,u}wv,u。m mm个部门分布在节点上各有需求d i d_idi。每次运输从1 11出发到某部门再返回消耗往返损耗之和。运输可行当且仅当执行时剩余能量≥ g o i max ( b a c k i , d i ) \geq go_i \max(back_i, d_i)≥goimax(backi,di)g o i go_igoi为去程损耗b a c k i back_ibacki为回程损耗。求总消耗不超过初始能量E EE时最多能满足的部门数量。这是一个反悔贪心问题关键在于按门槛排序后用堆维护已选任务实现用更优任务替换已选劣任务的贪心策略。算法选择DFS 预处理计算从节点1 11到每个节点的去程损耗g o i go_igoi和回程损耗b a c k i back_ibacki任务参数化对每个部门计算require go_i max(back_i, d_i)最低能量门槛和cost go_i back_i实际消耗反悔贪心 大根堆按require升序遍历任务能执行则执行并入堆不能执行则尝试用当前任务替换堆中cost最大的已选任务若替换后更优关键步骤建图与 DFS读入n , m , E n, m, En,m,E和n − 1 n-1n−1条边用邻接表存储双向不对称边从节点1 11DFS 计算所有节点的g o gogo和b a c k backback生成任务列表对每个部门若require E则加入tasks过滤不可行任务排序按require升序排序任务反悔贪心遍历若cur t.requirecur - t.cost将t.cost入堆否则若堆非空且pq.top() t.cost若cur pq.top() t.require则弹出堆顶cur cur pq.top() - t.cost将t.cost入堆输出堆的大小时间/空间复杂度时间复杂度O ( n m log m ) O(n m \log m)O(nmlogm)DFSO ( n ) O(n)O(n)排序O ( m log m ) O(m \log m)O(mlogm)堆操作O ( m log m ) O(m \log m)O(mlogm)空间复杂度O ( n m ) O(n m)O(nm)邻接表、任务列表、堆反悔贪心的核心思想门槛优先的贪心基线按require升序处理保证当前能量能执行的任务一定被考虑这是尽可能多完成任务的基础实际消耗的资源竞争总能量有限完成任务数最大化等价于在门槛约束下最小化总消耗堆维护替换候选大根堆存储已选任务的cost堆顶是消耗最大的任务。当遇到新任务无法执行时若其cost小于堆顶替换可减少总消耗可能释放足够能量执行更多任务延迟替换的正确性不立即替换所有可能情况而是在遍历过程中动态调整保证最终堆中任务是门槛约束下的最小消耗组合适用于在满足门槛约束的前提下用有限资源最大化任务数量的问题核心在于将任务量化为门槛消耗二元组通过排序和堆实现动态最优替换【算法标签】#反悔贪心【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglong// 将int定义为long long避免能量计算溢出constintN100005;// 定义数组最大容量为100005intn,m,E;// n为节点数m为部门数E为初始总能量structEdge{intv,go,back;// v为邻接节点go为从u到v的损耗back为从v到u的损耗};vectorEdgeadj[N];// adj[u]存储节点u的所有邻接边双向不对称损耗intgo[N],back[N];// go[i]为从节点1到i的去程总损耗back[i]为从i回到1的回程总损耗// 定义任务结构体每个部门运输所需的能量门槛和实际消耗structTask{intrequire,cost;// require为执行该运输所需的最低能量门槛cost为该运输的实际能量消耗};vectorTasktasks;// 存储所有可行的部门运输任务priority_queueintpq;// 大根堆存储已选任务的实际消耗用于后续替换优化// 深度优先搜索计算从节点1到每个节点的去程和回程总损耗voiddfs(intu,intfa){for(autox:adj[u])// 遍历u的所有邻接边{intvx.v,w1x.go,w2x.back;// v为邻接节点w1为u-v损耗w2为v-u损耗if(vfa)// 跳过父节点避免回溯continue;go[v]go[u]w1;// 累加去程损耗从1到v 从1到u u到vback[v]back[u]w2;// 累加回程损耗从v到1 从u到1 v到udfs(v,u);// 递归遍历子节点}}// 自定义排序按运输所需能量门槛升序排列贪心优先满足门槛低的部门boolcmp(Task x,Task y){returnx.requirey.require;}signedmain()// 使用signed main配合#define int long long{cinnmE;// 读入节点数、部门数、初始能量for(inti1;in;i)// 读入n-1条边的信息{intu,v,w1,w2;cinuvw1w2;adj[u].push_back({v,w1,w2});// u-v损耗w1v-u损耗w2adj[v].push_back({u,w2,w1});// v-u损耗w2u-v损耗w1}go[1]back[1]0;// 节点1为起点去程和回程损耗均为0dfs(1,0);// 从节点1开始DFS计算所有节点的go和back// 处理每个部门计算其运输任务参数for(inti1;im;i){intp,d;// p为部门所在节点d为部门能量需求cinpd;intgo_costgo[p];// 去程损耗intback_costback[p];// 回程损耗// 执行该运输的最低能量门槛去程损耗 max(回程损耗, 部门需求)// 因为到达时剩余能量必须≥需求d且还要能返回所以需要max(back, d)intrequirego_costmax(back_cost,(int)d);// 该运输的实际总消耗去程损耗 回程损耗能量只是门槛判断实际消耗是往返总和intcostgo_costback_cost;// 如果初始能量E足够满足该部门的最低门槛则该任务可行if(requireE)tasks.push_back({require,cost});// 加入可行任务列表}sort(tasks.begin(),tasks.end(),cmp);// 按门槛升序排序// 贪心堆优化尽可能多地满足部门需求intcurE;// cur记录当前剩余能量for(autot:tasks)// 按门槛从低到高遍历每个可行任务{if(curt.require)// 如果当前剩余能量足够执行该运输{cur-t.cost;// 扣除该运输的实际消耗pq.push(t.cost);// 将该任务的消耗加入大根堆}// 如果当前能量不足以执行新任务但可以用更省能量的任务替换已选任务elseif(!pq.empty()pq.top()t.cost)// 如果堆顶已选最大消耗大于当前任务消耗{inttmppq.top();// 取出堆顶消耗最大的已选任务// 如果替换后能量足够执行当前任务if(curtmpt.require){pq.pop();// 移除堆顶任务curcurtmp-t.cost;// 回收堆顶消耗扣除当前消耗更新剩余能量pq.push(t.cost);// 将当前任务加入堆}}}coutpq.size()endl;// 输出堆的大小即最多能满足的部门数量return0;}【运行结果】3 2 14 1 2 1 1 1 3 2 6 2 8 3 10 2