木桩 - 题解

标签与难度

标签: 数学, 思维题, 组合优化, 贪心, 二次函数, 推导难度: 1600

题目大意喵~

主人你好呀，喵~！这道题是这样的：我们有 a 个大木桩和 b 个小木桩，需要把它们全部放到一条直线上从 1 到 a+b 的位置上。

一种摆放方案的美观值由两个规则决定：

增加项: 任意两个大木桩（比如在位置 i 和 j），它们之间的小木桩数量会成为它们的贡献，加到总美观值里。
减少项: 任意一个大木桩（比如在位置 i），它后面（包括自己位置之后）的小木桩数量会从总美观值里减去。

我们的任务就是找到一种摆放方法，让这个美观值最大，然后告诉我这个最大值是多少，喵~

解题思路分析

这道题的计分规则看起来有点绕，尤其是要把所有大木桩对的贡献和每个大木桩的扣分项都加起来，感觉好复杂呀，喵... >.<

但是，我们可以换个角度思考问题！不要看大木桩，我们来关注一下每一根小木桩对总美观值的贡献，这样问题就会变得清晰起来~

想象一下，我们把一根小木桩放在了位置 p。

它会对哪些 “增加项” 产生贡献呢？一根小木桩要被计算在“增加项”里，它必须位于两个大木桩之间。如果我们把这根小木桩放在位置 p，那么在它左边有 L 个大木桩，右边有 R 个大木桩，它就会被 L \times R 对大木桩“夹在中间”。所以，它对“增加项”的总贡献就是 $L \times R$ 。
它又会对哪些 “减少项” 产生贡献呢？根据规则，每个在它前面的大木桩（共 L 个）都会因为它在后面而产生 -1 的扣分。所以，它对“减少项”的总贡献就是 $-L$ 。

把这两项合起来，一根小木桩放在一个左边有 L 个大木桩、右边有 R 个大木桩的位置，它的净贡献就是：

\text{Contribution} = L \times R - L

我们知道总共有 a 个大木桩，所以 $L+R=a$ 。于是 $R = a - L$ 。代入上面的公式，我们得到：

\text{Contribution} = L \times (a - L) - L = L \cdot a - L^2 - L = (a-1)L - L^2

这个公式只和 L（小木桩前面有多少个大木桩）有关，喵！

现在我们的目标就很明确了：我们有 b 个小木桩，要为它们每一个寻找一个位置，使得它们的总贡献最大。由于每个小木桩的贡献函数 $f(L) = (a-1)L - L^2$ 都是一样的，为了让总和最大，我们应该让每一个小木桩的贡献都最大化！

这意味着，我们应该把所有 b 个小木桩都放在贡献值最高的地方。也就是说，它们应该都拥有相同的 L 值。怎么才能做到呢？很简单，把所有小木桩都紧挨着放在一起，形成一个连续的块！

这样，我们的摆放方案就变成了这样： [k 个大木桩] [b 个小木桩] [a-k 个大木桩]

对于这个方案中所有的 b 个小木桩，它们前面都有 k 个大木桩。所以，总的美观值就是：

\text{Total Beauty} = b \times ((a-1)k - k^2)

现在问题就转化成了一个经典的数学问题：找到一个整数 k（ $0 \le k \le a$ ），使得函数 $g(k) = (a-1)k - k^2$ 的值最大。

这是一个开口向下的二次函数，喵~ 它的对称轴是 $k = \frac{-(a-1)}{2 \times (-1)} = \frac{a-1}{2}$ 。函数的最大值就在顶点处取得。因为 k 必须是整数，所以我们应该选择离对称轴 $\frac{a-1}{2}$ 最近的整数 k。

这两个整数就是 $\lfloor \frac{a-1}{2} \rfloor$ 和 $\lceil \frac{a-1}{2} \rceil$ 。幸运的是，无论 a 是奇数还是偶数，这两个点代入函数 $g(k)$ 的值都是一样的最大值。我们可以选择其中一个，比如 $k = \lfloor \frac{a-1}{2} \rfloor$ 。

所以，最大贡献值中 k 的部分可以这么计算：

\max_{k} \{ k(a-1-k) \} = \left\lfloor \frac{a-1}{2} \right\rfloor \times \left(a - 1 - \left\lfloor \frac{a-1}{2} \right\rfloor\right)

经过一点点代数小魔法，可以证明 $\left(a - 1 - \left\lfloor \frac{a-1}{2} \right\rfloor\right) = \left\lfloor \frac{a}{2} \right\rfloor$ 。（不信的话可以分 a 是奇数和偶数两种情况试试看哦，喵~）

所以，每个小木桩能产生的最大贡献是 $\lfloor \frac{a-1}{2} \rfloor \times \lfloor \frac{a}{2} \rfloor$ 。我们有 b 个小木桩，总的最大美观值就是：

\text{Max Beauty} = b \times \left\lfloor \frac{a-1}{2} \right\rfloor \times \left\lfloor \frac{a}{2} \right\rfloor

在 C++ 中，整数除法 (a-1)/2 和 a/2 天然就是向下取整的效果，所以最终的公式就非常简洁啦！

代码实现

这是我根据上面的思路，重新为您写的一份清晰的代码，喵~

cpp

#include <iostream>

// 使用 long long 防止计算结果溢出，因为 a 和 b 的值可能很大
// 乘积可能会超过普通 int 的范围
using ll = long long;

void solve() {
    ll a, b;
    std::cin >> a >> b;

    // 根据我们推导出的公式计算最大美观值，喵~
    // k1 表示最优策略下，放在小木桩堆前面的大木桩数量
    // 在C++中，整数除法自动实现向下取整，所以 (a-1)/2 就是 floor((a-1)/2)
    ll k1 = (a - 1) / 2;
    
    // k2 是与 k1 配对的另一个因子，(a/2) 对应 floor(a/2)
    ll k2 = a / 2;
    
    // 每个小木桩的最大贡献是 k1 * k2
    // b 个小木桩的总贡献就是 b * k1 * k2
    ll max_beauty = b * k1 * k2;
    
    std::cout << max_beauty << std::endl;
}

int main() {
    // 为了让输入输出更快一点，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析

时间复杂度: $O(1)$ 对于每一组测试数据，我们都只需要进行几次简单的算术运算。计算量是恒定的，与输入 a 和 b 的大小无关，所以时间复杂度是常数级别的，超级快，喵！
空间复杂度: $O(1)$ 我们只需要几个变量来存储输入和计算结果，没有使用任何额外的、随输入规模增长的数据结构。所以空间复杂度也是常数级别的。

知识点总结

这道题真有趣，从一个看似复杂的组合问题，变成了一个优美的数学问题，喵~

视角转换: 解决问题的关键在于将 "计算所有大木桩的贡献" 转换为 "计算每个小木桩的贡献"。这种改变视角的思维方式在很多算法题中都非常有用！
二次函数优化: 问题最终归结为求一个二次函数 $g(k) = (a-1)k - k^2$ 在整数定义域上的最大值。熟悉二次函数的性质（开口方向、对称轴、顶点）是解决这类问题的基础。
贪心思想: 当我们发现每个小木桩的贡献函数是独立且相同时，我们可以贪心地让每个小木桩都取到最大贡献值。这引导我们得出了将所有小木桩聚集在一起的策略。
整数除法: 在编程实现时，巧妙地利用 C++ 等语言中整数除法自动向下取整的特性，可以使代码非常简洁，直接对应了数学公式中的 $\lfloor \cdot \rfloor$ 符号。

希望我的题解能帮到你，如果还有问题，随时可以再来问我哦，喵~ O(∩_∩)O

木桩 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

代码实现 ​

复杂度分析 ​