专栏文章

题解：P13457 [GCJ 2008 #1A] Minimum Scalar Product

aabc1234shi
P13457题解参与者 4已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@miopygl8
此快照首次捕获于
2025/12/02 23:14
3 个月前
此快照最后确认于
2025/12/02 23:14
3 个月前
查看原文

分析

题目就相当于给出两个序列，让你两个序列每次都各给出一个数，两两相乘。把积加起来，求这些积的和的最小值。
最小值这不一眼贪心吗？那要如何贪心呢？我们来分析分析。

前置知识

一个很常用的数学理论，两数和一定时，差越大，积越小。

思路

那么我们使每次相乘的数的差尽可能的大，那么它们的积就最小了，积最小了，所有积的和不就最小了吗？

思路实现

将两个序列，一个从大到小排序，一个从小到大排序。
接下来将每一项都拿出来相乘。因为两个序列一个从大到小，一个从小到大排序了。那么对于从大到小排序的序列，第一项最大，最后一项最小。对于从小到大排序的序列，第一项最小，最后一项最大。
那么每一项相乘就是当前从大到小排序的序列的最大值乘上当前从小到大排序的序列的最小值，不就满足我们的思路了吗？
再将所有相乘的积相加，不就是要求的答案了吗？

注意

  • 乘积最大值 101010^{10}，乘积最小值 −1010-10^{10}，开 long long。
  • 如果你开的是全局数组，注意清空。
  • 注意换行。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
bool cmp(long long a, long long b) {
	return a > b;
}
int main() {
	int T;
	cin >> T;
	for (int j = 1; j <= T; j++) {
		int n;
		cin >> n;
		long long a[805], b[805];
		for (int i = 1; i <= n; i++) cin >> a[i];
		for (int i = 1; i <= n; i++) cin >> b[i];
		sort(a + 1, a + n + 1);
		sort(b + 1, b + n + 1, cmp);
		long long s = 0;
		for (int i = 1; i <= n; i++) s += a[i] * b[i];
		cout << "Case #" << j << ": " << s << '\n';
	}
	return 0;
}

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...