Skip to content

11341: 【原1341】songwennuan

题目

题目描述

author: Online Judge 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1341 ## 题目描述

死神又来送温暖了,友善的死神最喜欢送温暖了!

给你两个数组a[]和b[],他们有相同的长度n,你可以任意对a[]和b[]进行重排列,我们定义函数

$$ x = \sum a[i] * b[i] $$

现在,死神请你告诉他,x最大可以取到多少,最小可以取到多少?

是不是有种似曾相识的感觉?对了,这就是上个星期的第一题。

不准在程序中使用stl,不准使用sort,不准在程序前贴很长很长的模板,不准使用任何死神没有想到但是不能用的东西!

输入说明

第一行一个整数n,代表数组长度;

第二行数组a,最后一行数组b;

输出说明

输出两个整数代表答案;

Sample Input

2
10 3
10 9

Sample Output

127 120

数据范围

对于40%的数据,\( n \leq 10 \);

对于100%的数据,\( n \leq 100000,1 \leq a[i],b[i] \leq 100000 \);

yyong119's solution

#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_N = 100010;

int main() {

    ios::sync_with_stdio(false);
    int n; cin >> n;
    int a[MAX_N], b[MAX_N];
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n; ++i) cin >> b[i];
    sort(a, a + n);
    sort(b, b + n);
    long long maxx = 0, minx = 0;
    for (int i = 0; i < n; ++i) {
        maxx += (long long) a[i] * b[i];
        minx += (long long) a[i] * b[n - i - 1];
    }
    cout << maxx << " " << minx << endl;
    return 0;
}