题意：
给定两个数列 \(A\) 、 \(B\) ，元素个数分别为 \(n\) ， \(m\) \((2 \le n,m \le 50)\) 。数列中所有元素大小均在 \(-10^{9}\) 到 \(10^{9}\) 之间。
现要求在 \(A\) 数列中删掉一个元素，使得 \(A\) 中任一元素和 \(B\) 中任一元素相乘的共 \((n-1) \times m\) 种可能的值中的最大值最小。输出该最大值。
题解：
其实这题的 \(n, m\) 都可以开大到 \(10^6\)。
我的做法是 \(O(n+m)\) 的贪心。
先考虑不拿走元素的情况。那么对答案有贡献的元素只有可能是 \(A,B\) 中最大的元素和最小的元素。可以证明。
假设在 \(B\) 中挑了一个元素的值为 \(k\)，那么最终得出的这个值 \(y\) 与在 \(A\) 中挑出的元素 \(x\) 成正比例关系：\(y = kx\)。
这时候可以分类：
当 \(k>0\) 时，\(y\) 随 \(x\) 的增大而增大。所以当 \(x\) 取最大值时，\(y\) 才会是最大值。
当 \(k=0\) 时，无论 \(x\) 取何值，\(y\) 的值都为 \(0\)。此时我们可以当做取了最大值或最小值。
当 \(k<0\) 时，\(y\) 随 \(x\) 的增大而减小。所以当 \(x\) 取最小值时，\(y\) 才会是最大值。
终上所述，当 \(x\) 取最大值或最小值时，\(y\) 存在最大值。
所以我们应该挑 \(A\) 中最大或最小的元素。\(B\) 同理。
那么 \(y\) 的最大值为 \(\max(Max_A \cdot Max_B, Max_A \cdot Min_B, Min_A \cdot Max_B, Min_A \cdot Min_B)\)。
有 \(Max_A \cdot Max_B\) 和 \(Min_A \cdot Min_B\) 很好想到，那么为什么还要 \(Max_A \cdot Min_B\) 和 \(Min_A \cdot Max_B\) 呢？
有一组数据：
3 3
-3 -2 -1
1 2 3
显然答案一定是负数，为了使答案最大，这个值的绝对值应该越小。这样，就出现了 \(Max_A \cdot Min_B\) 了。
再考虑删除的情况。为了删除后的最大值最小，肯定拿走的数要对答案有贡献，那么就一定是 \(Max_A\) 或者 \(Min_A\)。此时 \(Maxer_A\) 和 \(Miner_A\) 就分别成为了 \(A\) 的最大值和 \(A\) 的最小值。再分别拿走 \(Max_A\)、\(Min_A\)，并分别用 \(Maxer_A\)、\(Miner_A\) 代替，代入上方公式，取较小值，就是最后答案了。
最大值、次大值、最小值、次小值在输入时就可以求出，不需要再花费 \(n log n\) 的排序，也可以节省空间。
时间复杂度仅有 \(O(n+m)\)。
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long llt;
const llt INF = 0x7F7F7F7F7F7F7F7F;
int n, m;
llt Max1 = -INF, Maxer1 = -INF, Min1 = INF, Miner1 = INF, Max2 = -INF, Min2 = INF;
void init() {
scanf("%d %d", &n, &m);
}
void solve() {
for (int i = 1; i <= n; ++i) {
llt x;
scanf("%lld", &x);
if (x > Max1) {
Maxer1 = Max1;
Max1 = x;
} else if (x > Maxer1)
Maxer1 = x;
if (x < Min1) {
Miner1 = Min1;
Min1 = x;
} else if (x < Miner1)
Miner1 = x;
}
for (int i = 1; i <= m; ++i) {
llt x;
scanf("%lld", &x);
Min2 = min(Min2, x);
Max2 = max(Max2, x);
}
//拿走值最大的元素
llt ans1 = max( max(Maxer1 * Max2, Maxer1 * Min2), max(Min1 * Max2, Min1 * Min2) );
//拿走值最小的元素
llt ans2 = max( max(Max1 * Max2, Max1 * Min2), max(Miner1 * Max2, Miner1 * Min2) );
llt ans = min(ans1, ans2);
printf("%lld\n", ans);
}
int main() {
init();
solve();
return 0;
}