在算法竞赛出题标准中，优秀的测试数据不仅要覆盖常规的随机情况，还要专门针对边界条件（Edge Cases） 和 特殊构造（Special Constructions） 进行精准打击。

为了在你的 OJ (Online Judge) 系统上完美运行，我设计了一套包含 10 个测试点 的数据生成方案。这个 C++ 生成器不仅会输出 .in 文件，还会直接调用我们之前写好的最优解代码，同步计算并生成对应的 .out 标准答案文件。

🎯 1~10 号测试点设计蓝图 (精准打击每一个易错点)

为了保证能够区分出选手的各种错误，我精心设计了这 10 个测试点的“剧本”：

1. Test 1 & 2：样例数据。保证选手只要能过样例就能拿到这两分，用于测试最基础的正确性。
2. Test 3：极小规模边界 (N=1, K=1)。专门拦截没有处理初始化、或者出现下标越界（i < j）等基础逻辑漏洞的代码。
3. Test 4：单一划分边界 (K=1, N=100)。测试 K=1 时，程序是否能够直接正确求出整个数组的均值，部分选手的代码如果内部循环没写好，这里会返回 0 或者越界。
4. Test 5：全划分边界 (K=N=100)。此时每个元素自成一段，答案应为原数组总和。测试选手在极端条件下的转移正确性。
5. Test 6：小规模随机 (N=20, K=5)。测试基本的动态规划逻辑。
6. Test 7：极限规模 + 少划分 (N=100, K=3)。
7. Test 8：极限规模 + 多划分 (N=100, K=50)。测试普通随机状态下的正确性和时间复杂度（时间复杂度不对的代码在这里会显出原形，但对 $N=100$ 而言都能轻松秒杀）。
8. Test 9：单调递增序列 (N=100, K=10)。这是一个防贪心 (Anti-Greedy) 测试点。很多选手可能会错误地使用贪心算法（比如每次切最大的数），单调序列最容易让贪心策略翻车，逼迫他们必须写 DP。
9. Test 10：全相同元素 (N=100, K=20, A_i=10000)。考验浮点数精度极限和无脑计算。所有数字相同，无论怎么切平均值之和都是固定的，一旦浮点运算中途丢失精度，这里必然报错！

💻 完整数据生成器 C++ 代码 (generator.cpp)

请在本地将以下代码保存为 generator.cpp，并使用 C++14 或更高标准编译运行。它会在同一目录下瞬间生成 1.in 到 10.out 共 20 个文件。文件体积非常小（KB 级别），绝对符合你的 OJ 需求。

#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>
#include <string>
#include <random>
#include <algorithm>
#include <cassert>

using namespace std;

// ---------------------------------------------------------
// 核心解题函数：用于生成标准答案 (.out 文件)
// 采用标准的二维 DP，绝对稳定，避免任何潜在的越界和除0错误
// ---------------------------------------------------------
double solveDP(int n, int k, const vector<int>& a) {
    vector<double> prefix(n + 1, 0.0);
    for (int i = 1; i <= n; ++i) {
        prefix[i] = prefix[i - 1] + a[i - 1]; // 注意: a 是 0-based
    }

    // 初始化 DP 表，设为极小值
    vector<vector<double>> dp(n + 1, vector<double>(k + 1, -1e9));
    
    // Base Case: K = 1 的情况
    for (int i = 1; i <= n; ++i) {
        dp[i][1] = prefix[i] / i;
    }

    // 状态转移
    for (int j = 2; j <= k; ++j) {
        for (int i = j; i <= n; ++i) {
            for (int x = j; x <= i; ++x) {
                double avg = (prefix[i] - prefix[x - 1]) / (i - x + 1);
                dp[i][j] = max(dp[i][j], dp[x - 1][j - 1] + avg);
            }
        }
    }
    return dp[n][k];
}

// ---------------------------------------------------------
// 主生成器逻辑
// ---------------------------------------------------------
int main() {
    // 使用固定的随机种子，保证每次生成的数据一致，方便复现和查错
    mt19937 rng(19980512); 

    for (int t = 1; t <= 10; ++t) {
        int n, k;
        vector<int> a;
        
        // --- 构建测试用例 ---
        if (t == 1) {
            // Test 1: 样例 1
            n = 5; k = 3;
            a = {9, 1, 2, 3, 9};
        } 
        else if (t == 2) {
            // Test 2: 样例 2
            n = 7; k = 4;
            a = {1, 2, 3, 4, 5, 6, 7};
        } 
        else if (t == 3) {
            // Test 3: 最小边界
            n = 1; k = 1;
            a = {9999};
        } 
        else if (t == 4) {
            // Test 4: K=1 边界
            n = 100; k = 1;
            uniform_int_distribution<int> dist(1, 10000);
            for(int i=0; i<n; ++i) a.push_back(dist(rng));
        } 
        else if (t == 5) {
            // Test 5: K=N 全划分边界
            n = 100; k = 100;
            uniform_int_distribution<int> dist(1, 10000);
            for(int i=0; i<n; ++i) a.push_back(dist(rng));
        } 
        else if (t == 6) {
            // Test 6: 小规模随机
            n = 20; k = 5;
            uniform_int_distribution<int> dist(1, 100);
            for(int i=0; i<n; ++i) a.push_back(dist(rng));
        } 
        else if (t == 7) {
            // Test 7: 极限规模 + 少划分
            n = 100; k = 3;
            uniform_int_distribution<int> dist(1, 10000);
            for(int i=0; i<n; ++i) a.push_back(dist(rng));
        } 
        else if (t == 8) {
            // Test 8: 极限规模 + 多划分
            n = 100; k = 50;
            uniform_int_distribution<int> dist(1, 10000);
            for(int i=0; i<n; ++i) a.push_back(dist(rng));
        } 
        else if (t == 9) {
            // Test 9: 严格单调递增 (防贪心/防假算法)
            n = 100; k = 10;
            for(int i=1; i<=n; ++i) {
                a.push_back(i * 100); // 100, 200, 300 ... 10000
            }
        } 
        else if (t == 10) {
            // Test 10: 极限相同元素 (测试浮点数精度丢失问题)
            n = 100; k = 20;
            for(int i=0; i<n; ++i) {
                a.push_back(10000);
            }
        }

        // --- 写入 .in 文件 ---
        string in_filename = to_string(t) + ".in";
        ofstream fout_in(in_filename);
        if (!fout_in.is_open()) {
            cerr << "无法创建文件: " << in_filename << endl;
            return 1;
        }
        
        fout_in << n << " " << k << "\n";
        for (int i = 0; i < n; ++i) {
            fout_in << a[i] << (i == n - 1 ? "" : " ");
        }
        fout_in << "\n";
        fout_in.close();

        // --- 运行标准程序并写入 .out 文件 ---
        string out_filename = to_string(t) + ".out";
        ofstream fout_out(out_filename);
        if (!fout_out.is_open()) {
            cerr << "无法创建文件: " << out_filename << endl;
            return 1;
        }

        // 调用解题函数计算答案
        double ans = solveDP(n, k, a);
        
        // NOI 竞赛标准：保留 6 位小数
        fout_out << fixed << setprecision(6) << ans << "\n";
        fout_out.close();

        cout << "Test " << t << " Generated Successfully! (N=" << n << ", K=" << k << ")" << endl;
    }

    cout << "All 10 test cases generated successfully in the current directory!" << endl;
    return 0;
}

💡 生成器复杂度与稳定性报告

• 时间复杂度评估：最耗时的是调用 solveDP 函数。其复杂度上限为 $O(N^2K)$，对于最大的测试点 $N=100, K=100$，运算次数约 $100 \times 100 \times 100 = 10^6$ 次。10 个测试点加起来也就几百万次运算，在现代 CPU 上执行时间远小于 0.05秒。完全不需要使用任何剪枝，即刻生成。
• 空间占用评估：生成的文本文件内容极少（最大仅为包含100个数字的纯文本），全部 1.in ~ 10.out 文件加在一起体积不到 20 KB，完美契合你“文件尽可能小（2MB内）”的要求。
• 稳定性：全部采用非递归（Bottom-Up DP）生成标准答案，绝无爆栈风险。并且区间计算时保证了 $x \le i$，故分母 $(i-x+1)$ 恒大于等于 1，绝对不会触发除以零 (Division by Zero) 异常。

作为你的教练，我非常高兴看到你准备好硬磕代码了。在算法竞赛（NOIP/CSP等）中，从“脑中有思路”到“手下能AC”，这中间隔着无数个细节陷阱（如越界、精度、初始化）。

为了让你真正吃透这道题，我将带你经历一个**“从朴素到极致”的三阶进化过程**。我们将按照 记忆化搜索 (DFS) $\rightarrow$ 标准二维 DP $\rightarrow$ 空间压缩一维 DP 的顺序，为你呈现 C++14 竞赛标准的完整代码。

请仔细阅读代码中的 // [关键点] 和 // [易错点] 注释，这是考场上最容易失分的地方！

版本一：记忆化搜索 (Top-Down DP)

教练点评：这是最符合人类直觉的版本。我们用递归函数 dfs(i, j) 表示“将前 i 个元素划分为 j 段的最大得分”。为了防止重复计算，我们加一个备忘录 memo。

#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>

using namespace std;

const int MAXN = 105;
const double INF = 1e9;

int n, k;
double a[MAXN];
double prefix[MAXN];
double memo[MAXN][MAXN];

// 求解将前 i 个元素，恰好划分为 j 段的最大平均值和
double dfs(int i, int j) {
    // [易错点 1] 边界条件：如果元素个数小于段数，绝对不可能划分，返回极小值
    if (i < j) return -INF;
    
    //[关键点 1] 递归终点：只划分 1 段，直接计算平均值
    if (j == 1) {
        return prefix[i] / i; 
    }
    
    // 如果已经计算过，直接返回备忘录里的值
    if (memo[i][j] > -1) {
        return memo[i][j];
    }
    
    double max_score = -INF;
    //[关键点 2] 尝试所有可能的最后一段的起点 x
    // 因为前面还要留 j-1 段，所以前面至少需要 j-1 个元素，即起点 x 最小为 j
    for (int x = j; x <= i; ++x) {
        // [关键点 3] 前缀和 O(1) 计算区间 [x, i] 的平均值
        double current_avg = (prefix[i] - prefix[x - 1]) / (i - x + 1);
        max_score = max(max_score, dfs(x - 1, j - 1) + current_avg);
    }
    
    return memo[i][j] = max_score;
}

int main() {
    // 竞赛标准：优化 C++ I/O 速度
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    if (!(cin >> n >> k)) return 0;
    
    // 为了防止下标“差一错误”，我们统一使用 1-based 索引 (1 到 N)
    prefix[0] = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        prefix[i] = prefix[i - 1] + a[i];
    }
    
    // 初始化备忘录为 -1 (因为题目数字都是正数，平均值和必然大于0，-1代表未访问)
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= k; ++j) {
            memo[i][j] = -1.0;
        }
    }
    
    // 输出并保留 6 位小数
    cout << fixed << setprecision(6) << dfs(n, k) << "\n";
    
    return 0;
}

• 时间复杂度：状态总数 $O(N \times K)$，每个状态需要遍历 $O(N)$ 个起点 $x$。总时间复杂度 $O(N^2 K)$。
• 空间复杂度：备忘录二维数组 $O(N \times K)$ + 递归调用栈深度 $O(K)$。总空间复杂度 $O(NK)$。

版本二：标准二维 DP (Bottom-Up)

教练点评：递归会产生额外的函数调用开销。我们将版本一的逻辑“倒过来”，从小规模往大规模推导，这就是讲义中推崇的标准二维 DP 模板。

#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k;
    if (!(cin >> n >> k)) return 0;
    
    vector<double> a(n + 1, 0.0);
    vector<double> prefix(n + 1, 0.0);
    
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        prefix[i] = prefix[i - 1] + a[i];
    }
    
    //[关键点 1] 初始化 DP 表。大小为 (n+1) x (k+1)，初始值为负无穷
    // dp[i][j] 表示前 i 个元素分成 j 段的最大得分
    vector<vector<double>> dp(n + 1, vector<double>(k + 1, -1e9));
    
    // [易错点 1] Base Case: 初始化 j = 1 的情况（单独成段）
    // 注意：0个元素分0段通常是0，但这里我们直接从 j=1 开始铺垫地基更稳妥
    for (int i = 1; i <= n; ++i) {
        dp[i][1] = prefix[i] / i;
    }
    
    // [关键点 2] 三重嵌套循环：外层枚举段数 j，中层枚举前缀长度 i，内层枚举分割点 x
    for (int j = 2; j <= k; ++j) {
        for (int i = j; i <= n; ++i) {
            //[易错点 2] x 表示最后一段的起点，[x, i] 是最后一段
            // 为保证前 x-1 个元素足够分 j-1 段，x-1 必须 >= j-1，即 x >= j
            for (int x = j; x <= i; ++x) {
                double last_group_avg = (prefix[i] - prefix[x - 1]) / (i - x + 1);
                // 状态转移
                dp[i][j] = max(dp[i][j], dp[x - 1][j - 1] + last_group_avg);
            }
        }
    }
    
    cout << fixed << setprecision(6) << dp[n][k] << "\n";
    return 0;
}

• 时间复杂度：严格的三重循环，$O(N^2 K)$。
• 空间复杂度：二维 DP 表 dp[N+1][K+1]，$O(NK)$。

版本三：空间压缩一维 DP (最优版)

教练点评：考场上如果 $N=5000, K=5000$，版本二的二维数组会消耗巨大内存（甚至超限）。仔细观察转移方程 dp[i][j] = max(dp[i][j], dp[x-1][j-1] + ...)，计算第 j 层（当前层）只用到了第 j-1 层（上一层）的数据。我们完全可以用一个一维数组搞定！

#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k;
    if (!(cin >> n >> k)) return 0;
    
    vector<double> a(n + 1, 0.0);
    vector<double> prefix(n + 1, 0.0);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        prefix[i] = prefix[i - 1] + a[i];
    }
    
    // [关键点 1] 降维打击：只开一个长度为 N+1 的一维数组
    // 初始状态相当于填入 j=1 时的那一列数据
    vector<double> dp(n + 1, 0.0);
    for (int i = 1; i <= n; ++i) {
        dp[i] = prefix[i] / i;
    }
    
    for (int j = 2; j <= k; ++j) {
        // [致命易错点 1] 必须逆序遍历 i ！！！
        // 为什么？因为计算新的 dp[i] 时，需要用到未更新的 dp[x-1] (其中 x-1 < i)。
        // 如果正序遍历，前面的 dp[x-1] 会被提前覆盖成第 j 层的新值，产生逻辑污染！
        for (int i = n; i >= j; --i) {
            
            double max_val = -1e9; // 用临时变量存当前 i 劈分的最大值
            
            for (int x = j; x <= i; ++x) {
                double last_group_avg = (prefix[i] - prefix[x - 1]) / (i - x + 1);
                // [关键点 2] 此时的 dp[x-1] 是纯正的“上一轮(j-1)”遗留下来的值
                max_val = max(max_val, dp[x - 1] + last_group_avg);
            }
            // 扫描完所有分割点后，安全地更新当前 i 的值
            dp[i] = max_val;
        }
    }
    
    cout << fixed << setprecision(6) << dp[n] << "\n";
    return 0;
}

• 时间复杂度：依然是三重循环嵌套，$O(N^2 K)$。
• 空间复杂度：仅使用了一维 dp 数组和 prefix 数组，极致压缩到了 $O(N)$！

🏆 教练总结与优化思考过程回顾

在这三段代码中，你能清晰地看到算法优化的路径：

1. 如何优化时间？ 最原始的暴力如果要在循环里求均值是 $O(N^3 K)$。我们看到 区间和/均值 这种需求，条件反射般地加上了 前缀和 (Prefix Sum) 技巧，使得区间代价计算变成了 $O(1)$，直接消灭了一个量级。
2. 如何优化空间？ 我们画出 DP 表的依赖拓扑图，发现当前行的更新严格依赖于其左上方的元素（dp[x-1][j-1]，其中 x-1 < i）。利用这种无后效性的单向依赖，我们通过倒序遍历 i 的方式，砍掉了 j 这个维度，完美实现空间压缩。

现在，你已经掌握了这个模板的终极形态。请把版本三的代码闭卷敲一遍。