11338: 【原1338】puzzle

题目

题目描述

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

萌萌的死神最讨厌数学题了，讨厌讨厌真是讨厌死了。

这不，死神一生的好朋友gingkgo又拿数学题来难为他了。接到题目后，死神原本眉飞色舞的脸瞬间石化了，真是讨厌死了。

幸亏还有你们这群好朋友呢！如果没有的话，事情才不知道会怎么样呢！

现在问题来了，给你2个数组a[]和b[]，他们有相同的长度n，你可以任意交换一个数组中的元素，我们定义函数

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

现在，死神请你告诉他，x最大可以取到多少，最小可以取到多少？真是讨厌死了。

输入说明

第一行一个整数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 \)；

ligongzzz's solution

#include "iostream"
#include "cstdio"
using namespace std;

void myMergeSort(int* data, int num) {
    if (num == 0) return;
    else if (num == 1) return;

    myMergeSort(data, num / 2);
    myMergeSort(data + num / 2, num - num / 2);

    //合并
    int* temp = new int[num];

    for (int i = 0, j = num / 2, n = 0; i < num / 2 || j < num; n++) {
        if (i < num / 2 && j < num) {
            if (data[i] < data[j]) {
                temp[n] = data[i];
                i++;
            }
            else {
                temp[n] = data[j];
                j++;
            }
        }
        else if (i == num / 2) {
            temp[n] = data[j];
            j++;
        }
        else if (j == num) {
            temp[n] = data[i];
            i++;
        }
    }

    //复制
    for (int i = 0; i < num; i++)
        data[i] = temp[i];

    delete temp;
}

int A[100009], B[100009];

int main() {
    int len;
    cin >> len;

    for (int i = 0; i < len; ++i)
        scanf("%d", &A[i]);
    for (int i = 0; i < len; ++i)
        scanf("%d", &B[i]);

    myMergeSort(A, len);
    myMergeSort(B, len);

    //计算
    unsigned long long ans = 0;
    for (int i = 0; i < len; ++i)
        ans += (long long)A[i] * (long long)B[i];
    cout << ans << " ";
    ans = 0;
    for (int i = 0; i < len; ++i)
        ans += (long long)A[i] * (long long)B[len - i - 1];
    cout << ans;

    return 0;
}

q4x3's solution

/**
 * 归并排序
 * 排序不等式
 * 注意long long
 **/
#include <iostream>

using namespace std;
long long n, a[100233], b[100233], inf, sup;

template <typename T>
void merge(int lo, int mi, int hi, T* a)
{
    T* A = a + lo;
    int lb = mi - lo;
    T* B = new T[lb];
    T* BB = B;
    for(int i = 0;i < lb;++ i)
        B[i] = A[i];
    int lc = hi - mi;
    T* C = a + mi;
    int cnt = 0;
    while(1) {
        if ((lb == 0) && (lc == 0)) break;
        if (lb == 0) {
            A[cnt] = C[0];
            ++ cnt; ++ C; -- lc;
        }
        else if (lc == 0) {
            A[cnt] = B[0];
            ++ cnt; ++ B; --lb;
        }
        else {
            if(B[0] < C[0]) {
                A[cnt] = B[0];
                ++ cnt; ++ B; -- lb;
            }
            else {
                A[cnt] = C[0];
                ++ cnt; ++ C; -- lc;
            }
        }
    }
    delete []BB;
}

template <typename T>
void mergeSort(int lo, int hi, T* A)
{
    if(hi - lo < 2) return;
    int mi = (lo + hi) / 2;
    mergeSort(lo, mi, A); mergeSort(mi, hi, A);
    merge(lo, mi, hi, A);
}

int main()
{
    cin >> n;
    for (int i = 0;i < n;++ i) cin >> a[i];
    for (int i = 0;i < n;++ i) cin >> b[i];
    mergeSort(0, n, a); mergeSort(0, n, b);
    for (int i = 0;i < n;++ i)
        sup += a[i] * b[i];
    for (int i = 0;i < n;++ i)
        inf += a[i] * b[n - i - 1];
    cout << sup << " " << inf << endl;
    return 0;
}

skyzh's solution

#include <iostream>
#include <algorithm>
using namespace std;

int a[100000], b[100000];

int main() {
    int n;
    cin >> 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 _min = 0, _max = 0;
    for (int i = 0; i < n; i++) {
        _max += (long long) a[i] * b[i];
        _min += (long long) a[i] * b[n - i - 1];
    }
    cout << _max << " " << _min << endl;
    return 0;
}

victrid's solution

#include <iostream>

using namespace std;

long int* MergeSort(long int* list, int listSize) {
    if (listSize == 1)
        return list;
    if (listSize == 2) {
        if (list[0] > list[1]) {
            long int temp = list[0];
            list[0]  = list[1];
            list[1]  = temp;
            return list;
        }
        return list;
    }
    long int* tmplist = new long int[listSize];
    long int* llst    = MergeSort(list, listSize / 2);
    long int* rlst    = MergeSort(list + listSize / 2, listSize - listSize / 2);
    int lct = 0, rct = 0;
    while (lct + rct != listSize) {
        if ((llst[lct] <= rlst[rct] && lct < listSize / 2) || rct >= listSize - listSize / 2) {
            tmplist[lct + rct] = llst[lct];
            lct++;
        } else {
            tmplist[lct + rct] = rlst[rct];
            rct++;
        }
    }
    for (int i = 0; i < listSize; i++)
        list[i] = tmplist[i];

    return list;
}

int main() {
    //Chebyshyov neravyenctvo
    int m;
    cin >> m;
    //! MUST BE A LONG INT!
    long int* l1 = new long int[m];
    long int* l2 = new long int[m];
    for (int i = 0; i < m; i++) {
        cin >> l1[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> l2[i];
    }
    MergeSort(l1, m);
    MergeSort(l2, m);

    // for (int i = 0; i < m; i++) {
    //     cout << l1[i] << ' ';
    // }
    long int max = 0, min = 0;
    for (int i = 0; i < m; i++) {
        max += l1[i] * l2[i];
        min += l1[i] * l2[m - i - 1];
    }
    cout << max << ' ' << min;
    return 0;
}

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