这是一个功能完善的 C++ 数据生成器。它集成了标准题解逻辑（用于生成 .out）和针对不同测试点要求的数据构造逻辑（用于生成 .in）。

运行一次即可自动生成 1.in/1.out 到 10.in/10.out，涵盖了 40%、70%、100% 数据范围，以及“无解”、“大容量单品”、“大花费”等边界情况。

数据生成器代码 (C++14)

/**
 * B3873 [GESP202309 六级] 小杨买饮料 - 数据生成器
 * 功能：生成 1.in/1.out ~ 10.in/10.out
 * 作者：OI教练
 */

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdlib>
#include <ctime>

using namespace std;

// ==========================================
// Part 1: 标准题解逻辑 (用于生成 .out)
// ==========================================
const int INF = 0x3f3f3f3f;
const int MAXL_SOLVE = 2005; // 对应 L 的最大值 2000
int dp[MAXL_SOLVE];

struct Drink {
    int c, l; // cost, volume
};

string solve(int n, int target_l, const vector<Drink>& drinks) {
    // 初始化 DP 数组
    memset(dp, 0x3f, sizeof(dp));
    dp[0] = 0;

    for (const auto& drink : drinks) {
        // 倒序遍历
        for (int j = target_l; j >= 0; j--) {
            if (dp[j] == INF) continue;
            
            // 状态转移，超过 L 的都算作 L
            int next_vol = min(target_l, j + drink.l);
            if (dp[next_vol] > dp[j] + drink.c) {
                dp[next_vol] = dp[j] + drink.c;
            }
        }
    }

    if (dp[target_l] == INF) {
        return "no solution";
    } else {
        return to_string(dp[target_l]);
    }
}

// ==========================================
// Part 2: 数据构造工具
// ==========================================

// 生成 [min, max] 范围内的随机整数
int randInt(int min, int max) {
    if (min > max) return min;
    return rand() % (max - min + 1) + min;
}

// ==========================================
// Part 3: 测试点生成逻辑
// ==========================================
void makeData(int fileId) {
    string inName = to_string(fileId) + ".in";
    string outName = to_string(fileId) + ".out";
    ofstream fin(inName);
    ofstream fout(outName);

    int N, L;
    vector<Drink> drinks;

    // -------------------------------------------------
    // 40% 数据范围: N <= 20, L <= 100, li <= 100
    // -------------------------------------------------
    if (fileId == 1) {
        // 基础测试：小规模，必然有解
        N = 5; L = 100;
        for(int i=0; i<N; i++) drinks.push_back({randInt(1, 10), randInt(20, 50)});
    }
    else if (fileId == 2) {
        // 基础测试：小规模，构造“无解”情况
        // 总容量加起来都不够 L
        N = 5; L = 100;
        for(int i=0; i<N; i++) drinks.push_back({randInt(1, 10), randInt(1, 10)}); // sum max 50 < 100
    }
    else if (fileId == 3) {
        // 边界测试：恰好满足 L
        N = 10; L = 100;
        int current_sum = 0;
        for(int i=0; i<N-1; i++) {
            int v = randInt(1, 10);
            drinks.push_back({randInt(1, 10), v});
            current_sum += v;
        }
        // 最后一个凑够 100
        if (current_sum < 100) drinks.push_back({randInt(1, 10), 100 - current_sum});
        else drinks.push_back({randInt(1, 10), 1});
    }
    // -------------------------------------------------
    // 70% 数据范围: li <= 100 (N, L 变大)
    // -------------------------------------------------
    else if (fileId == 4) {
        // 中等规模
        N = 50; L = 500;
        for(int i=0; i<N; i++) drinks.push_back({randInt(10, 100), randInt(1, 100)});
    }
    else if (fileId == 5) {
        // 单个物品体积很小，需要很多个才能凑齐
        N = 100; L = 1000;
        for(int i=0; i<N; i++) drinks.push_back({randInt(1, 5), randInt(1, 10)});
    }
    // -------------------------------------------------
    // 100% 数据范围: N <= 500, L <= 2000, ci, li <= 10^6
    // -------------------------------------------------
    else if (fileId == 6) {
        // 特殊情况：存在“单瓶容量极大”的饮料 (li >= L)
        // 测试 min(L, j+v) 逻辑是否正确
        N = 10; L = 100;
        drinks.push_back({10, 2000}); // 一瓶就够，看是否选它
        for(int i=0; i<N-1; i++) drinks.push_back({randInt(1, 5), randInt(1, 10)});
    }
    else if (fileId == 7) {
        // 边界测试：N=1
        N = 1; L = 100;
        // 有解
        drinks.push_back({100, 150});
    }
    else if (fileId == 8) {
        // 边界测试：N=1 无解
        N = 1; L = 100;
        drinks.push_back({100, 50});
    }
    else if (fileId == 9) {
        // 压力测试：花费很大 (接近 10^6)
        // 测试是否会溢出 (虽然本题 int 够用，但这是好习惯)
        N = 500; L = 2000;
        for(int i=0; i<N; i++) drinks.push_back({randInt(900000, 1000000), randInt(100, 2000)});
    }
    else { // fileId == 10
        // 综合压力测试：完全随机大数
        N = 500; L = 2000;
        for(int i=0; i<N; i++) drinks.push_back({randInt(1, 10000), randInt(1, 3000)});
    }

    // 写入输入文件
    fin << N << " " << L << endl;
    for (const auto& d : drinks) {
        fin << d.c << " " << d.l << endl;
    }

    // 计算并写入输出文件
    fout << solve(N, L, drinks) << endl;

    fin.close();
    fout.close();
    cout << "Generated Case " << fileId << ": N=" << N << ", L=" << L << endl;
}

int main() {
    // 初始化随机数种子
    srand((unsigned)time(NULL));

    for (int i = 1; i <= 10; i++) {
        makeData(i);
    }
    
    cout << "All 10 test cases generated successfully!" << endl;
    return 0;
}

数据分布说明 (符合教练出题标准)

你可以直接编译运行这段代码，它会在当前目录下生成符合 OJ 标准的测试数据文件。

这是一个符合 NOIP C++14 竞赛标准的题解代码。

核心思路

1. 模型识别：这是一个 0/1 背包问题 的变种。
   • 限制：每个物品（饮料）只能选一次。
   • 目标：总容量 $\ge L$ 的前提下，总花费最小。
   • 不同点：普通背包是“体积 $\le V$ 求最大价值”，这里是“体积 $\ge L$ 求最小花费”。
2. 状态定义：
   • 定义 dp[j] 为：获得总容量至少为 j 毫升时所需的最少花费。
   • 状态压缩（关键点）：由于我们只关心是否达到了目标 $L$，所以对于所有超过 $L$ 的体积，我们都将其视为 $L$。因此数组只需要开到 $L+1$。
3. 初始化：
   • 求最小值，所以 dp 数组初始化为一个极大值（INF），表示“尚未达到该状态”。
   • dp[0] = 0，表示容量为 0 时花费为 0。
4. 状态转移：
   • 遍历每个物品 $(c, v)$。
   • 倒序遍历 j 从 $L$ 到 $0$（0/1 背包的标准操作，防止重复选取同个物品）。
   • 如果不选该物品：状态不变。
   • 如果选该物品：当前状态 dp[j] 可以转移到 dp[min(L, j + v)]。
   • 转移方程：dp[next_v] = min(dp[next_v], dp[j] + c)。

标准代码 (C++14)

/**
 * 题目：B3873 [GESP202309 六级] 小杨买饮料
 * 考点：0/1 背包、动态规划 (求最小代价)
 * 难度：普及/提高-
 */

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring> // 用于 memset

using namespace std;

// 定义一个极大值，代表无解或初始无穷大
// 0x3f3f3f3f 是竞赛常用的无穷大常数，约为 10^9，相加不易溢出且可用 memset 赋值
const int INF = 0x3f3f3f3f;

// 题目中 L 最大为 2000，开 2005 足够
const int MAXL = 2005;
int dp[MAXL];

void solve() {
    int n, target_l;
    if (!(cin >> n >> target_l)) return;

    // 关键点1：初始化 DP 数组
    // 我们要求的是“最小花费”，所以初始化为无穷大
    memset(dp, 0x3f, sizeof(dp));
    
    // 容量为 0 时，花费自然是 0
    dp[0] = 0;

    // 读入每个物品并进行 DP 转移
    for (int i = 0; i < n; i++) {
        int cost, vol; // c_i, l_i
        cin >> cost >> vol;

        // 关键点2：0/1 背包必须倒序遍历
        // 如果正序遍历，同一个物品可能会被累加多次（变成完全背包）
        // 我们遍历的是“当前已有的容量状态 j”
        for (int j = target_l; j >= 0; j--) {
            // 如果 dp[j] 是 INF，说明还凑不出容量 j，无法从这里转移
            if (dp[j] == INF) continue;

            // 计算加上当前饮料后的新容量
            // 关键点3：超过 target_l 的部分都归为 target_l
            // 这样可以保证数组下标不越界，且符合题目“不低于 L”的要求
            int next_vol = min(target_l, j + vol);

            // 状态转移：取更小的花费
            // 这一步使用了 long long 的思维，但由于 cost 和 dp 值都在 int 范围内，
            // 且 10^9 + 10^6 不会爆 int，所以这里用 int 没问题。
            // 题目最大花费估计：500 * 10^6 = 5*10^8 < 2*10^9 (INT_MAX)
            if (dp[next_vol] > dp[j] + cost) {
                dp[next_vol] = dp[j] + cost;
            }
        }
    }

    // 关键点4：输出结果判断
    // 如果 dp[target_l] 仍然是 INF，说明无法凑出至少 L 的容量
    if (dp[target_l] == INF) {
        cout << "no solution" << endl;
    } else {
        cout << dp[target_l] << endl;
    }
}

int main() {
    // 竞赛标准 IO 优化
    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

    return 0;
}

易错点解析

1. 数组大小与状态定义：
   • 题目中饮料单瓶容量 $l_i$ 可达 $10^6$。如果直接用最大容量开 DP 数组 (dp[1000000])，不仅空间浪费，而且遍历时间会超时。
   • 正解：根据题目要求“不低于 $L$”，我们将所有 $\ge L$ 的状态都映射到 dp[L]。这样数组大小仅需 $L+1$（即 2000 左右），时间复杂度为 $O(N \times L)$，非常高效。
2. 循环顺序：
   • for (int j = target_l; j >= 0; j--)。必须倒序！
   • 如果正序遍历，当你计算 dp[50] 时用了这瓶饮料，稍后计算 dp[100] 时可能又利用了刚刚更新过的 dp[50]，导致这瓶饮料被买了两次。
3. INF 的选择：
   • 使用 0x3f3f3f3f 是竞赛老手的习惯。它足够大（约 $10^9$），且 INF + INF 不会溢出 int，还支持 memset（按字节赋值）。
4. No Solution 的判断：
   • 不要直接输出 dp[L]，题目明确要求可能无解。必须判断是否等于初始值。

你好！我是你的OI教练。很高兴看到你在攻克 GESP 六级的题目。这道题是背包问题的一个变种，非常经典，但也藏着几个容易踩的坑。

这道题不再是简单的“容量限制下求最大价值”，而是反过来了：“需求限制下求最小代价”。

我们还是老规矩，拿出草稿纸，把思路一层层剥开。

1. 读题关键词：你的“雷达”响了吗？

读题时，这几个关键词决定了你的算法模型，请务必圈出来：

1. “每种饮料至多购买 1 瓶”：
   • 核心暗示：这是典型的 0/1 背包问题 模型。每个物品只有拿或不拿两种选择。
2. “总容量不低于 $L$”：
   • 状态定义的变化：通常背包问题是“体积不超过 $V$”，这里是“体积至少为 $L$”。
   • 思考：如果我拿了 20000 毫升，虽然远超 $L$，但也是满足条件的。所以，所有大于 $L$ 的体积，其实都可以看作是 $L$（满足了就行）。
3. “尽可能少的费用”：
   • 目标函数：我们要计算的是 min(cost)，而不是 max(value)。
   • 初始化：求最小值时，数组通常要初始化为“无穷大”，而不是 0。
4. “$N \le 500, L \le 2000$” vs “$l_i \le 10^6$”：
   • 数据范围陷阱：$N$ 和 $L$ 很小，但单个饮料的容量 $l_i$ 可能非常大。
   • 结论：你的 DP 数组大小应该由 $L$ 决定，而不是由 $l_i$ 的最大值决定。千万不要开 $10^6$ 大小的数组，那是浪费空间且容易超时的。

2. 预备知识点

要解决这道题，你需要掌握：

• 0/1 背包问题的滚动数组优化：将二维 DP 压成一维，注意循环顺序是从大到小。
• DP 初始化技巧：求最小值（Min）问题，初始状态设为 INF（一个很大的数），起点的 dp[0] 设为 0。
• 边界处理：如何处理体积溢出 $L$ 的情况。

3. 启发式教学：草稿纸上的推演

我们要建立一个数组 dp，dp[j] 表示获得至少 j 毫升饮料所需的最小花费。（或者理解为：获得正好 j 毫升，对于超过 $L$ 的都归入 dp[L]）。

定义状态：

• dp[j]：凑出体积 $j$ 所需要的最少钱数。
• 特别地，当体积 $\ge L$ 时，我们将它统一存放在 dp[L] 中。

初始化：

• 我们想求最小值，所以先把 dp 数组全填满 999999999（表示如果不买饮料，不可能凑出这些体积）。
• 唯独 dp[0] = 0（凑出 0 毫升不需要花钱）。

推导过程（以样例 1 为例）： 目标 $L=100$。 DP 数组大小为 101 (0~100)。

• 第 1 瓶 (花费100, 容量2000)：

  • 如果我们选它，容量变成 2000。因为 $2000 > 100$，我们把它记在 dp[100] 上。
  • dp[100] 更新为 min(原值, dp[0] + 100) = 100。
  • 现在：dp[100]=100, 其他是无穷大。

• 第 2 瓶 (花费2, 容量50)：

  • 我们从大到小遍历 $j$（从 $L$ 到 $0$）。
  • 对于 dp[100]：如果不选是 100；如果选（假设之前有 50 的状态），但之前 dp[50] 是无穷大，没用。
  • 对于 dp[50]：可以由 dp[0] 转移而来。dp[50] = min(INF, dp[0] + 2) = 2。
  • 注意：如果 $j=100$，我们要看 dp[100-50]。
  • 但是这里有个特殊的**推法（刷表法思维）**可能更容易理解：
    • 遍历当前已知的状态 $j$（从 $L$ 到 $0$）。
    • 如果 dp[j] 是有效值（不是无穷大），那我们可以加上这瓶饮料。
    • 新体积 next_v = j + 50。
    • 关键点：如果 next_v 超过了 $L$，就把它当成 $L$。即 next_v = min(L, j + 50)。
    • 更新：dp[next_v] = min(dp[next_v], dp[j] + 2)。

让我们用这个逻辑重跑一遍：

4. 核心逻辑梳理 (伪代码思路)

1. 定义：dp 数组大小为 $L+1$（下标 0 到 $L$）。
2. 初始化：dp 全为 INF，dp[0] = 0。
3. 循环：
   • 外层循环遍历每一个饮料 $i$（花费 $c$, 体积 $v$）。
   • 内层循环 $j$ 从 $L$ 倒序遍历到 $0$。
     • 为什么要倒序？ 因为这是 0/1 背包，防止同一瓶饮料在同一次外层循环中被累加多次。
     • 计算加入这瓶饮料后的体积：$t = \min(L, j + v)$。
     • 核心转移方程：dp[t] = min(dp[t], dp[j] + c)。
     • 注意：只有当 dp[j] 不是 INF 时才转移。
4. 结果：
   • 检查 dp[L]。
   • 如果 dp[L] 还是 INF，说明凑不出 $L$，输出 no solution。
   • 否则输出 dp[L]。

5. 易错点总结

1. 数组大小：不要开到 $10^6$，开到 $L+1$ (即 2005) 就够了。
2. 状态压缩：任何超过 $L$ 的体积都视为 $L$。代码里要写 min(L, j + v)。
3. No Solution：题目说了如果不能满足要输出 no solution。这不仅包括买光了都不够的情况，也包括 dp[L] 没被更新的情况。
4. 数据类型：虽然这题花费加起来不太可能爆 int（$500 \times 10^6$ 约为 $5 \times 10^8$，int 是 $2 \times 10^9$），但为了保险起见，建议开 long long，或者 INF 设为 0x3f3f3f3f (约 $10^9$) 即可。

加油！拿起笔，把那个表格画一画，你就能写出最完美的代码！