题意简述
给定数组 \(a\) 和 \(b\),可以交换下标相同的两个元素。让 \(a\) 数组的最大值和 \(b\) 数组的最大值之积最小。
分析
想象一个长方形,它的周长是固定的,那怎么分配长和宽才能让面积尽可能的小呢?
就假设周长是 \(18\),则长宽之和是 \(9\),列下表格:
长 | 宽 | 面积 |
---|---|---|
1 | 8 | 8 |
2 | 7 | 14 |
3 | 6 | 18 |
4 | 5 | 20 |
观察长和宽的差值,分别是 \(7,5,3,1\),而面积不断地增大。
所以我们可以得出结论:
两个数和一定,差越大,积越小。
回到题目,题目要求积要尽可能地小,所以我们让 \(a\) 数组的数尽可能地大,\(b\) 数组的数尽可能地小,再分别求最大值,就能得出答案了。
代码实现
#include <bits/stdc++.h>
using namespace std;
int t;
int n;
int a[105];
int b[105];
int main(){
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
int s1=0,s2=0;
for(int i=1;i<=n;i++){
if(a[i]<b[i])swap(a[i],b[i]);
s1=max(s1,a[i]);s2=max(s2,b[i]);
}
cout<<s1*s2<<endl;
}
return 0;
}