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