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

· · 题解

题意

给定 2n 个数，求两两相乘积之和的最小值。

重要结论

对于任意正整数 a，b，n（1\le a < b < n），有：

(n+a)(n-a)>(n+b)(n-b)

由于本题数据都是正整数，因此在正整数范围内证明即可。

证明：原式 =n^2-a^2>n^2-b^2。

整理，得 a^2<b^2。

因为有 a<b，所以 a^2<b^2成立。

故原命题成立。

分析

通过前面的证明我们知道，要求出一个序列中两两相乘积之和的最小值，只需要把给定序列的最小值乘最大值，第 i 小的值乘第 i 大的值即可，但是因为给定的序列不一定有序，所以我们先要从小到大排序。

注意：数组长度为 2n，且由于数据范围较大，要开 long long。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;            //用 ll 替代 long long，可以减少代码长度
ll a[200005],n,ans;
int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n*2;i++){
        scanf("%lld",&a[i]);
    }
    sort(a+1,a+2*n+1);           //进行排序，注意有 2n 个数要进行排序
    for(int i=1;i<=n;i++){
        ans+=a[i]*a[2*n-i+1];    //计算积之和的最小值
    }
    printf("%lld",ans);
    return 0;
}