题解：P12218 [蓝桥杯 2023 国 Java B] 玩具

\(\mathbf{upd\ 2025/5/31}\)：修正标点，修正语病与小逻辑问题，修正 \(\LaTeX\) 中使用符号的不当之处，减少了一些没必要的啰嗦话。

思路与算法

思路

在写这道题的代码之前，我注意到，既然要使权重和最小，那就不能让大的和大的（权重）相乘，小的和小的（权重）相乘，最后再加起来，这个思路是正确的。\(%#### 即：\)\(%#### 1. 小的乘小的、大的乘大的策略：\)\(%如果我们按照“小的乘小的”的策略，将较小的零件配对，会导致较大的权重值被直接累加到总和中。\)\(%#### 2. 小的乘大的策略：\)\(%如果我们采用“小的乘大的”的策略，将最小的零件与最大的零件配对，可以有效地平衡权重的贡献。因为较小的零件与较大的零件相乘，其结果会比两个较大的零件相乘更小。\)

——为什么？我们来看一看。

首先，我们看样例说明的操作（策略），发现有这样的规律。

那让我们先来看看简单情况。

首先，设有四个零件重量 \(a \le b \le c \le d\)，我们比较两种配对方式的权重和：

1.小的乘小的、大的乘大的：

2.小的乘大的：

我们知道，比大小，只要看相减之后，式子是正是负就可以了。

所以，让我们展开并比较 \((a \times b) + (c \times d)\) 与 \((a \times d) + (b \times c)\) 的差值，

为：

不完全化简得：

由于

所以 \((a - c)\) 和 \((b - d)\) 均为非正数，它们的乘积 \((a - c) \times (b - d)\) 为非负数。

即：

又

因此：

这表明，在零件个数为 \(4\) 时，“小的乘大的”的策略总是优于“小的乘小的、大的乘大的”的策略。

接着，我们不断拓宽：\(8\) 个零件、\(12\) 个零件、\(16\) 个零件等。

同时，我们注意到，当 \(n\) 取奇数时，第 \((n+1) \div 2\) 组刚好是中间的那一组。
这时，无论我们选用“小的乘小的、大的乘大的”还是“小的乘大的”的策略，第 \((n+1) \div 2\) 组总是相等的，也就是说，当组数为奇数时，我们可以忽略中间的一组，并把它作为组数为偶数，即零件个数为 \(4\) 的倍数的情况来处理。

因此，“小的乘大的”的策略总是优于“小的乘小的、大的乘大的”的策略。

算法：

明白了上面的内容，接下来找我们要使用的算法就很简单了。

查看算法标签，发现算法为“贪心”、“排序”和“双指针 two-pointer”，所以算法就是用这两个。

由于我们这里要一定使小的乘大的，因此，我们需要用到贪心的算法。又因为我们要知道什么是小的，什么是大的，我们就需要通过排序，使小的分布在最前面，大的分布在最后面。同时，已经用过的积木不能被第二次使用，我们需要使用双指针来判断我们现在正在计算的积木的重量的下标。

代码

由于权重是很多数的乘积的和，所以不要忘了把数据类型开大一点。我令总权重为cnt，让我们试一试最差情况：当 \(n\) 最大，\(m_i\)、\(m_j\) 最大时，\(cnt=n\times(m_i \times m_j) = 10^5 \times 10^5 \times 10^5 = 10^{15}\)。它超过了 int 类型的最大值（\(%2^{31}-1，\)约 \(2.14748\times10 ^ 9\)），而 long long 类型则可以记录（\(%2^{63}-1，\)约 \(9.22337\times10 ^ {18}\)）。又因为权重都为非负数，我们可以使用无符号类型。因此，我们在这里可以选用的数据类型（C 与 C++ 环境下）有 unsigned int、long long、unsigned long long。

最后简单附上我的代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#include<bits/stdc++.h>
using namespace std;
long long n, w[200005], cnt = 0; // cnt 表示权重
int main(){
    scanf("%lld", &n); 
    for(int i = 0; i < 2 * n; i++)
        scanf("%d", &w[i]); 
    sort(w, w+(2*n)); 
    int i = 0, j = 2*n-1; 
    while(i < j){ 
        cnt += w[i] * w[j]; 
        i++, j--;
    }
    printf("%lld", cnt); 
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

using System;
using System.Linq;

class Program
{
    static void Main()
    {
        long n = int.Parse(Console.ReadLine()); 
        long[] w = Console.ReadLine().Split().Select(long.Parse).ToArray(); 
        Array.Sort(w); 
        long cnt = 0; // 权重
        long i = 0, j = 2 * n - 1; 
        while (i < j) 
        {
            cnt += w[i] * w[j]; 
            i++;
            j--;
        }
        Console.WriteLine(cnt); 
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

import java.util.Arrays;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong(); 
        long[] w = new long[(int)(2 * n)]; 
        for (int i = 0; i < 2 * n; i++) {
            w[i] = sc.nextLong(); 
        }
        Arrays.sort(w); 
        long cnt = 0; // 权重
        int i = 0, j = (int)(2 * n) - 1; 
        while (i < j) { 
            cnt += w[i] * w[j]; 
            i++;
            j--;
        }
        System.out.println(cnt); 
        sc.close();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

import sys
n = int(input())  
w = list(map(int, input().split()))  
w.sort()  
cnt = 0  # 权重
i, j = 0, 2 * n - 1  
while i < j:  
    cnt += w[i] * w[j]  
    i += 1
    j -= 1
print(cnt)