对比之美

[题目链接](https://www.nowcoder.com/practice/0fcbb83370124426bfee75aca43b7ee7)

思路

给定 $n$ 个格子和 $m$ 个收藏品，要求将收藏品放入格子中（每个格子放 $\geq 0$ 个），使美观度 $\sum_{i=1}^{n-1} |a_i - a_{i+1}|$ 最大。

分类讨论

$n = 1$ ：没有相邻对，美观度为 $0$ 。

$n = 2$ ：将所有 $m$ 个收藏品放在一个格子，另一个放 $0$ ，美观度为 $m$ 。

$n \geq 3$ ：将所有 $m$ 个收藏品放在某个中间位置（非端点），例如 $[0, m, 0, \ldots]$ ，该位置与左右邻居各产生 $m$ 的差值，美观度为 $2m$ 。

为什么 $2m$ 是上界？注意每个收藏品对美观度的贡献最多为 $2$ （它所在格子最多参与两个相邻对的差值），所以总美观度 $\leq 2m$ 。当 $n \geq 3$ 时，把所有物品放在一个非端点格子恰好达到这个上界。

复杂度

时间复杂度： $O(1)$ 每组数据
空间复杂度： $O(1)$

代码

C++

#include <bits/stdc++.h>
using namespace std;
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        long long n,m;
        scanf("%lld%lld",&n,&m);
        long long ans;
        if(n==1) ans=0;
        else if(n==2) ans=m;
        else ans=2*m;
        printf("%lld%c",ans,t?' ':'\n');
    }
    return 0;
}

Java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < t; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine().trim());
            long n = Long.parseLong(st.nextToken());
            long m = Long.parseLong(st.nextToken());
            long ans;
            if (n == 1) ans = 0;
            else if (n == 2) ans = m;
            else ans = 2 * m;
            if (i > 0) sb.append(' ');
            sb.append(ans);
        }
        System.out.println(sb.toString());
    }
}