企业官网建设流程全解析

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

学而思编程：小明的U盘

【题目描述】

在 2202 年的某一天，小明得到了一个高端 U 盘。

但是小明发现这个 U 盘有一些问题：

这个 U 盘的传输接口大小是L LL，只能传输大小不超过L LL的文件。

这个 U 盘容量是S SS，一共只能装不超过S SS的文件。

但是他要备份的资料却有很多，你只能备份其中的一部分。

共有n nn个文件，第i ii个文件的大小和价值为w i , v i w_i,v_iwi​,vi​。小明很快发现他不可能把所有文件装进优盘，好在这是一个高端的 U 盘，他可以花钱升级接口大小、或者升级容量。每花1 11元可以将接口大小增加1 11，每花1 11元可以将 U 盘容量增加1 11。

注意：你的文件不能被分割（你只能把一个文件整个的传输进去，并储存在U盘中），你放在 U 盘中文件的总大小不能超过 U 盘容量。

现在问题来了：小明只有m mm元，他想知道，他最多可能将多大价值的文件放入 U 盘中。

【输入】

第1 11行，4 44个正整数n , m , L , S n,m,L,Sn,m,L,S。

第2 22行，n nn个正整数w 1 , w 2 , ⋯ , w n w_1,w_2,⋯ ,w_nw1​,w2​,⋯,wn​。

第3 33行，n nn个正整数v 1 , v 2 , ⋯ , v n v_1,v_2,⋯ ,v_nv1​,v2​,⋯,vn​。

【输出】

1 11个整数，最多可以放入 U 盘的文件总价值。

【输入样例】

5 9 4 4 6 9 9 5 6 8 7 9 1 5

【输出样例】

9

【核心思想】

1. 问题分析：给定n nn个文件（大小w i w_iwi​，价值v i v_ivi​），U盘初始接口大小L LL、容量S SS，预算m mm元。每花1元可将接口或容量增加1。文件大小必须同时满足：不超过接口大小（才能传输）和不超过U盘容量（才能存储）。可以选择升级接口使某个大文件能够传输，求在预算内能装入的最大总价值。这是一个01背包变体问题，关键在于枚举哪个文件享受接口升级优惠。

2. 算法选择：

   • 01背包：dp[i][j]表示前i ii个文件，花费不超过j jj的最大价值
   • 枚举优惠券使用：排序后枚举哪个文件使用接口升级

3. 关键步骤：

   • 按大小排序：将文件按w i w_iwi​从小到大排序，保证枚举时前面文件都能通过当前接口
   • 01背包DP：总可用资金 = 初始容量S SS+ 预算m mm
     • dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])（选或不选第i ii个文件）
   • 枚举升级使用：对于排序后的第i ii个文件：
     • 升级接口后的实际大小：cost = max(w[i] - L, 0)（升级后大小为L LL，原大小w [ i ] w[i]w[i]需要升级w [ i ] − L w[i]-Lw[i]−L）
     • 剩余容量给其他文件：S + m - cost
     • 答案更新：ans = max(ans, dp[i][S + m - cost])

4. 时间/空间复杂度：

   • 时间复杂度：O ( n × ( S + m ) + n log ⁡ n ) O(n \times (S+m) + n \log n)O(n×(S+m)+nlogn)，排序O ( n log ⁡ n ) O(n \log n)O(nlogn)，背包O ( n × ( S + m ) ) O(n \times (S+m))O(n×(S+m))
   • 空间复杂度：O ( n × ( S + m ) ) O(n \times (S+m))O(n×(S+m))

5. 01背包变体（带优惠券抵扣）的核心思想：

   • 排序预处理：按文件大小排序，确保枚举时前面文件都能通过当前接口大小
   • 枚举策略：枚举哪个文件使用接口升级优惠，其余文件使用普通容量
   • 费用计算：升级接口后的实际占用 =max(原大小 - 接口大小, 0)
   • 容量分配：总资源 = 初始容量 + 预算，分配给升级文件和普通文件
   • 适用于带单一优惠选择的背包问题

【算法标签】

#01背包

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=505;intn,m,l,s,dp[N][20005],ans;// dp: 背包DP数组, ans: 最终答案structnode{intw,v;// w: 原价, v: 价值}a[N];// 按原价从小到大排序boolcmp(node x,node y){returnx.w<y.w;}intmain(){cin>>n>>m>>l>>s;for(inti=1;i<=n;i++){cin>>a[i].w;// 读取原价}for(inti=1;i<=n;i++){cin>>a[i].v;// 读取价值}sort(a+1,a+n+1,cmp);// 0/1背包：计算前i个物品，花费不超过j的最大价值for(inti=1;i<=n;i++){for(intj=1;j<=s+m;j++)// 总可用资金 = 初始资金s + 优惠券价值m{dp[i][j]=dp[i-1][j];// 不选第i个物品if(j>=a[i].w){// 选第i个物品dp[i][j]=max(dp[i][j],dp[i-1][j-a[i].w]+a[i].v);}}}// 枚举使用优惠券购买的商品ifor(inti=1;i<=n;i++){// 使用优惠券后的实际花费：原价 - 优惠券价值l，但不能为负intcost=max(a[i].w-l,0);ans=max(ans,dp[i][s+m-cost]);}cout<<ans;return0;}

【运行结果】

5 9 4 4 6 9 9 5 6 8 7 9 1 5 9