题目链接

GCJ 2008 R1A Minimum Scalar Product

思路

直觉大的跟小的相乘再求和值最小，这是一类贪心题，将a从小到达排序，将b从大到小排序，a与b一一对应配对，如果存在交叉情况，一定可以通过交换到不交叉更优。

注意long long

时间复杂度

$$ O(Nlog(N)) $$

代码

#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 1000;

int a[MAXN], b[MAXN];

int main() {
    int T;
    scanf("%d", &T);// don't forget &
    for (int kase = 1; kase <= T; kase++) {
        int n;
        scanf("%d", &n);// don't forget &
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);// don't forget &
        }
        for (int i = 1; i <= n; i++) {
            scanf("%d", &b[i]);// don't forget &
        }
        sort(a + 1, a + 1 + n);
        sort(b + 1, b + 1 + n);
        long long ans = 0;
        for (int i = 1; i <= n; i++) {
            ans += 1LL * a[i] * b[n - i + 1];
        }
        printf("Case #%d: %lld\n", kase, ans);
    }

    return 0;
}