题解 | #对比之美#

题目链接

对比之美

题目描述

小美有 $n$ 个格子和 $m$ 个收藏品。她需要将这 $m$ 个收藏品放入 $n$ 个格子中（允许空格子），目标是让摆放方案的“美观度”最大。美观度定义为所有相邻两个格子中收藏品数量之差的绝对值之和。

形式化地，设第 $i$ 个格子摆放了 $c_i$ 个收藏品，则需满足 $\sum_{i=1}^{n} c_i = m$ 且 $c_i \ge 0$ ，并最大化 $\sum_{i=2}^{n} |c_i - c_{i-1}|$ 。

思路分析

这是一个构造性的最优化问题。目标是最大化相邻元素差值的绝对值之和。

为了使差值最大化，我们应该让相邻格子的物品数量尽可能悬殊。最理想的情况是在一个值为 $0$ 的格子和一个值很大的格子之间产生对比。

我们可以将全部 $m$ 个收藏品视为一个整体，来分析如何放置能产生最大的美观度。

根据格子数量 $n$ 的不同，存在以下三种情况：

当 $n = 1$ 时：只有一个格子，不存在“相邻”的格子。因此，无论 $m$ 是多少，美观度的计算式为空，结果永远是 $0$ 。
当 $n = 2$ 时：我们有两个格子，设其物品数量为 $c_1$ 和 $c_2$ 。约束条件为 $c_1 + c_2 = m$ 。美观度为 $|c_2 - c_1|$ 。要最大化 $|c_2 - c_1|$ ，我们需要让 $c_1$ 和 $c_2$ 的差距尽可能大。最优的分配方案是将所有 $m$ 个物品都放在一个格子里，另一个格子为空。例如，令 $c_1 = m, c_2 = 0$ 。此时美观度为 $|0 - m| = m$ 。
当 $n > 2$ 时：当格子数量超过两个时，我们总可以找到一个“中间”的格子（即左右都有相邻格子的格子）。我们可以将所有 $m$ 个物品都集中放在一个中间格子里，比如第二个格子。这样形成的布局是 [0, m, 0, ...]。我们来计算这种布局的美观度：
- 第一个差值是 $|c_2 - c_1| = |m - 0| = m$ 。
- 第二个差值是 $|c_3 - c_2| = |0 - m| = m$ 。
- 所有其他的差值都是 $|0 - 0| = 0$ 。总的美观度为 $m + m = 2 \cdot m$ 。这个值是理论上的最大值，因为每个物品最多只能贡献两次差值（一次是它所在“堆”的左边界，一次是右边界）。

综上所述，我们可以根据 $n$ 的值直接得出答案。

代码

cpp
java
python

#include <iostream>

using namespace std;

int main() {
    int t;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        long long n, m;
        cin >> n >> m;
        if (i > 0) {
            cout << " ";
        }
        if (n == 1) {
            cout << 0;
        } else if (n == 2) {
            cout << m;
        } else {
            cout << 2 * m;
        }
    }
    cout << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for (int i = 0; i < t; i++) {
            long n = sc.nextLong();
            long m = sc.nextLong();
            if (i > 0) {
                System.out.print(" ");
            }
            if (n == 1) {
                System.out.print(0);
            } else if (n == 2) {
                System.out.print(m);
            } else {
                System.out.print(2 * m);
            }
        }
        System.out.println();
    }
}

t = int(input())
results = []
for _ in range(t):
    n, m = map(int, input().split())
    if n == 1:
        results.append("0")
    elif n == 2:
        results.append(str(m))
    else:
        results.append(str(2 * m))
print(" ".join(results))

算法及复杂度

算法：贪心 / 构造
时间复杂度：对于每组测试数据，我们只进行了一次判断，因此复杂度是 $O(1)$ 。总时间复杂度为 $O(T)$ ，其中 $T$ 是数据组数。
空间复杂度： $O(1)$ 。