Question

SWAP X
Bạn được cho hai dãy số nguyên dương aa và bb gồm nn phần tử mỗi mảng. Bạn được phép thực hiện thao tác này nhiều lần:

Chọn 1 số nguyên ii bất kỳ (1≤i≤n) và tráo đổi 2 phần tử a[i] và b[i].

Yêu cầu: Tìm giá trị nhỏ nhất có thể của max(a1,a2,...,an)⋅max(b1,b2,...,bn)sau khi bạn thực hiện thao tác trên 1 hoặc nhiều lần.

Dữ liệu:

Dòng đầu ghi t thể hiện số testcase, t≤100.

t block tiếp theo, mỗi block có dạng:

Dòng đầu ghi số nguyên dương n (n≤104).

Dòng thứ hai ghi nn số nguyên dương a1,a2,...,an (ai≤106)

Dòng thứ ba ghi nn số nguyên dương b1,b2,...,bn(bi≤106).

Kết quả:
Ứng với mỗi testcase, in ra kết quả cần tìm.
input
3
6
1 2 6 5 1 2
3 4 3 2 2 5
3
3 3 3
3 3 3
2
1 2
2 1
output
18
9
2

Answer 1

Ý tưởng: Tìm số lớn nhất trong hai dãy đã cho. Không mất tính tổng quát, giả sử số lớn nhất của 2 dãy nằm trong dãy a, ta xét các số trong dãy b, tại vị trí i:  nếu a[i] < b[i] thì hoán vị a[i] và b[i]. Sau đó tìm số lớn nhất trong dãy b rồi nhân với số lớn nhất của hai dãy sẽ ra được kết quả. 

#include <iostream>

using namespace std;

#define maxN 105

 

int main() {

int a[maxN], b[maxN];

int t;

cin >> t;

while (t--)

{

int n;

cin >> n;

int maxA = 0, maxB = 0;

for (int i = 0; i < n; i++)

{

cin >> a[i]; maxA = max(a[i], maxA);

}

for (int i = 0; i < n; i++)

{

cin >> b[i]; maxB = max(b[i], maxB);

}

if (maxA < maxB) 

swap(a, b);

int maxV = max(maxA, maxB);

for (int i = 0; i < n; i++)

if (b[i] > a[i]) 

swap(b[i], a[i]);

maxB = 0;

for (int i = 0; i < n; i++)

maxB = max(b[i], maxB);

cout << maxB * maxV << endl;

}

return 0;

}