题意：
给定两个数列 (A) 、 (B) ，元素个数分别为 (n) ， (m) ((2 le n,m le 50)) 。数列中所有元素大小均在 (-10^{9}) 到 (10^{9}) 之间。
现要求在 (A) 数列中删掉一个元素，使得 (A) 中任一元素和 (B) 中任一元素相乘的共 ((n-1) imes 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
", ans);
}
int main() {
init();
solve();
return 0;
}