本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。
欢迎大家订阅我的专栏：算法题解：C++与Python实现！
附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总
【题目来源】
学而思编程：小明的U盘
【题目描述】
在 2202 年的某一天，小明得到了一个高端 U 盘。
但是小明发现这个 U 盘有一些问题：
这个 U 盘的传输接口大小是
L
L
L，只能传输大小不超过
L
L
L 的文件。
这个 U 盘容量是
S
S
S，一共只能装不超过
S
S
S 的文件。
但是他要备份的资料却有很多，你只能备份其中的一部分。
共有
n
n
n 个文件，第
i
i
i 个文件的大小和价值为
w
i
,
v
i
w_i,v_i
wi,vi。小明很快发现他不可能把所有文件装进优盘，好在这是一个高端的 U 盘，他可以花钱升级接口大小、或者升级容量。每花
1
1
1 元可以将接口大小增加
1
1
1，每花
1
1
1 元可以将 U 盘容量增加
1
1
1。
注意：你的文件不能被分割（你只能把一个文件整个的传输进去，并储存在U盘中），你放在 U 盘中文件的总大小不能超过 U 盘容量。
现在问题来了：小明只有
m
m
m 元，他想知道，他最多可能将多大价值的文件放入 U 盘中。
【输入】
第
1
1
1 行，
4
4
4 个正整数
n
,
m
,
L
,
S
n,m,L,S
n,m,L,S。
第
2
2
2 行，
n
n
n 个正整数
w
1
,
w
2
,
⋯
,
w
n
w_1,w_2,⋯ ,w_n
w1,w2,⋯ ,wn。
第
3
3
3 行，
n
n
n 个正整数
v
1
,
v
2
,
⋯
,
v
n
v_1,v_2,⋯ ,v_n
v1,v2,⋯ ,vn。
【输出】
1
1
1 个整数，最多可以放入 U 盘的文件总价值。
【输入样例】
5 9 4 4
6 9 9 5 6
8 7 9 1 5
【输出样例】
9
【核心思想】
问题分析：给定
n
n
n 个文件（大小
w
i
w_i
wi，价值
v
i
v_i
vi），U盘初始接口大小
L
L
L、容量
S
S
S，预算
m
m
m 元。每花1元可将接口或容量增加1。文件大小必须同时满足：不超过接口大小（才能传输）和不超过U盘容量（才能存储）。可以选择升级接口使某个大文件能够传输，求在预算内能装入的最大总价值。这是一个01背包变体问题，关键在于枚举哪个文件享受接口升级优惠。
算法选择：
- 01背包：dp[i][j] 表示前
i
i
i 个文件，花费不超过j
j
j 的最大价值 - 枚举优惠券使用：排序后枚举哪个文件使用接口升级
关键步骤：
- 按大小排序：将文件按
w
i
w_i
wi 从小到大排序，保证枚举时前面文件都能通过当前接口 - 01背包DP：总可用资金 = 初始容量
S
S
S + 预算m
m
m- dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])（选或不选第
i
i
i 个文件）
- dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])（选或不选第
- 枚举升级使用：对于排序后的第
i
i
i 个文件：- 升级接口后的实际大小：cost = max(w[i] – L, 0)（升级后大小为
L
L
L，原大小w
[
i
]
w[i]
w[i] 需要升级w
[
i
]
−
L
w[i]-L
w[i]−L） - 剩余容量给其他文件：S + m – cost
- 答案更新：ans = max(ans, dp[i][S + m – cost])
- 升级接口后的实际大小：cost = max(w[i] – L, 0)（升级后大小为
时间/空间复杂度：
- 时间复杂度：
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))
01背包变体（带优惠券抵扣）的核心思想：
- 排序预处理：按文件大小排序，确保枚举时前面文件都能通过当前接口大小
- 枚举策略：枚举哪个文件使用接口升级优惠，其余文件使用普通容量
- 费用计算：升级接口后的实际占用 = max(原大小 – 接口大小, 0)
- 容量分配：总资源 = 初始容量 + 预算，分配给升级文件和普通文件
- 适用于带单一优惠选择的背包问题
【算法标签】
#01背包
【代码详解】
#include<bits/stdc++.h>
using namespace std;
const int N = 505;
int n, m, l, s, dp[N][20005], ans; // dp: 背包DP数组, ans: 最终答案
struct node
{
int w, v; // w: 原价, v: 价值
} a[N];
// 按原价从小到大排序
bool cmp(node x, node y)
{
return x.w < y.w;
}
int main()
{
cin >> n >> m >> l >> s;
for (int i = 1; i <= n; i++)
{
cin >> a[i].w; // 读取原价
}
for (int i = 1; i <= n; i++)
{
cin >> a[i].v; // 读取价值
}
sort(a + 1, a + n + 1, cmp);
// 0/1背包：计算前i个物品，花费不超过j的最大价值
for (int i = 1; i <= n; i++)
{
for (int j = 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);
}
}
}
// 枚举使用优惠券购买的商品i
for (int i = 1; i <= n; i++)
{
// 使用优惠券后的实际花费：原价 – 优惠券价值l，但不能为负
int cost = max(a[i].w – l, 0);
ans = max(ans, dp[i][s + m – cost]);
}
cout << ans;
return 0;
}
【运行结果】
5 9 4 4
6 9 9 5 6
8 7 9 1 5
9
