题目描述

难度分:$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$的数据规模太小了，直接暴力枚举可做：

1. 枚举删除$a$中的哪个元素$a[k]$。
2. 然后双重循环枚举$a$中剩余元素与$b$中所有元素组成的数对$(a[i],b[j])$，计算出最大乘积$mx$。
3. 维护对于每个删除元素$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;
}