题目描述
难度分:$1400$
输入$n(2 \leq n \leq 50)$,$m(2 \leq m \leq 50)$和长为$n$的数组$a$,长为$m$的数组 $b$,元素范围$[-10^9,10^9]$。
你必须恰好删除$a$中的一个数字。最小化$a[i] \times b[j]$的最大值。输出这个最大值。
输入样例$1$
2 2
20 18
2 14
输出样例$1$
252
输入样例$2$
5 3
-1 0 1 2 3
-1 0 1
输出样例$2$
2
算法
暴力枚举
$a$和$b$的数据规模太小了,直接暴力枚举可做:
- 枚举删除$a$中的哪个元素$a[k]$。
- 然后双重循环枚举$a$中剩余元素与$b$中所有元素组成的数对$(a[i],b[j])$,计算出最大乘积$mx$。
- 维护对于每个删除元素$a[k]$的$mx$最小值即可。
复杂度分析
时间复杂度
枚举$a[k]$时间复杂度$O(n)$;枚举$a$中剩余元素和$b$中所有元素的组合$(a[i],b[j])$,时间复杂度为$O(nm)$;因此总的时间复杂度为$O(n^2m)$。
空间复杂度
除了输入的两个数组$a$和$b$,整个算法过程中只使用了有限几个变量,额外空间复杂度为$O(1)$。
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 55;
int n, m, a[N], b[N];
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
for(int i = 1; i <= m; i++) {
scanf("%d", &b[i]);
}
bool flag1 = false;
LL ans;
for(int k = 1; k <= n; k++) {
bool flag2 = false;
LL mx;
for(int i = 1; i <= n; i++) {
if(i == k) continue;
for(int j = 1; j <= m; j++) {
if(!flag2) {
mx = (LL)a[i]*b[j];
flag2 = true;
}else {
mx = max(mx, (LL)a[i]*b[j]);
}
}
}
if(!flag1) {
ans = mx;
flag1 = true;
}else {
ans = min(mx, ans);
}
}
printf("%lld\n", ans);
return 0;
}