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

· · 题解

分析

题目就相当于给出两个序列，让你两个序列每次都各给出一个数，两两相乘。把积加起来，求这些积的和的最小值。

最小值这不一眼贪心吗？那要如何贪心呢？我们来分析分析。

前置知识

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

思路

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

思路实现

将两个序列，一个从大到小排序，一个从小到大排序。

接下来将每一项都拿出来相乘。因为两个序列一个从大到小，一个从小到大排序了。那么对于从大到小排序的序列，第一项最大，最后一项最小。对于从小到大排序的序列，第一项最小，最后一项最大。

那么每一项相乘就是当前从大到小排序的序列的最大值乘上当前从小到大排序的序列的最小值，不就满足我们的思路了吗？

再将所有相乘的积相加，不就是要求的答案了吗？

注意

代码

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