题意

给定

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。

代码

CPP

#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;
}

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

文章操作

题意

重要结论

分析

代码

相关推荐

评论

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