# 11338: 【原1338】puzzle

### 题目描述

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

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

## Sample input

2
10 3
10 9


## Sample output

127 120


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