给定 数组A和Ｂ都是整数数组，各包括N个数，定义函数F(X,K),U(X)是最大值，D(X)是最小值，S(X)是差。
| F(X,K) | = | A[K]*X + B[K] |
| U(X) | = | max{ F(X,K) : 0 ≤ K < N } |
| D(X) | = | min{ F(X,K) : 0 ≤ K < N } |
| S(X) | = | U(X) − D(X) |
求min S(x) 这里x与结果都可以是任意实数。
其实这就是个线性分段函数的最小值问题。
范围： N [1..10^5]
A,B种的每个数[-10^3..+10^3]
复杂度要求： 时间O(NlogN),空间O(N)
分析： 这个题本身不难，求线性分段函数的极值，我们可以在每个段上分别考虑，因为每个段都是线性的，极值肯定在端点取到，枚举即可。但是它的复杂度很诡异，时间O(NlogN)，正好是排序的复杂度。我们先算U(x)，就是试图分段出x在不同区间时，它的样子。这个其实就是说判断它每种形式在不同区间的大小。 我们先把函数按斜率排序，斜率相等按截距排。 假设两段是 k1*x + b1和k2 * x + b2 k1 <= k2
如果k1 == k2 那么 b1, b2都直接决定了大小，也就是说 平行线的话，容易考虑。
如果k1 < k2，我们算出它的交点x1，那么再x < x1时k1 * x + b1大一些，x > x1 k2 * x + b2大一些。
同理下一段 k3 *x + b3 k2 < k3
我们同样求它和k2 * x + b2的交点 x2 ，如果我们发现x2 <= x1，也就是说这个交点比x1来得更早的话，第二段k2 * x + b2是没用的，它不可能是最大值，因为当它要成为最大值之前k3 * x + b3已经比它大了。于是我们把它扔掉就可以了，再用k3 * x + b3和更前一条直线求交点，这个过程就像保存了一个堆栈，每次可能把栈顶弹出来，如果弹出来还要继续判断。最终把当前段和交点压入堆栈。 还是那个道理，每段出入栈最多1次，所以这个复杂度是O(N)的。 （没算排序）。
其实D(X)也可以类似处理，取个相反数就好了。。。。
这个题难点一个在于分段函数极值，不能O(N^2),其实就是要求每条直线超过另外一条直线的位置。
还有一个难点在于最后结果的特殊判断，例如只有一段的话，极值点怎么取？ 还有所有直线都平行之类的特殊情况，所以我代码写得很长。
代码：
// you can also use includes, for example:// #include <algorithm>
#include <algorithm>
int cmp(pair<int,int> &a,pair<int,int> &b) {
return a.first * b.second - a.second * b.first;
}
pair<int,int> inter(pair<int,int> &a,pair<int,int> &b) {
return make_pair(b.second - a.second, a.first - b.first);
}
void make(vector<pair<int,int> > &all,vector<pair<int,int> > &p, vector<pair<int,int> > &line) {
int n = all.size(),i,j;
for (i = 0; i < n; ++i) {
for (j = i; (j < n) && (all[i].first == all[j].first); ++j)
;
i = j - 1;
if (line.empty()) {
line.push_back(all[i]);
}
else {
pair<int,int> temp;
for (j = line.size() - 1; j >= 0; --j) {
temp = inter(line[j], all[i]);
if (p.empty() || (cmp(temp, p.back()) > 0)) {
break;
}
p.pop_back();
line.pop_back();
}
p.push_back(temp);
line.push_back(all[i]);
}
}
}
double solution(vector<int> &A, vector<int> &B) {
// write your code here...
vector<pair<int,int> > all;
int i,j,n = A.size();
for (i = 0; i < n; ++i) {
all.push_back(make_pair(A[i],B[i]));
}
sort(all.begin(),all.end());
vector<pair<int,int> > U, UP;
make(all, UP, U);
for (i = 0; i < n; ++i) {
all[i].first = -all[i].first;
all[i].second = -all[i].second;
}
reverse(all.begin(), all.end());
vector<pair<int,int> > D, DP;
make(all, DP, D);
bool inf = true;
int c;
double r = 0,may;
for (i = j = 0;;) {
bool infi = (i >= UP.size()), infj = (j >= DP.size());
if (infi) {
if (infj) {
break;
}
else {
c = 1;
}
}
else if (infj) {
c = -1;
}
else {
c = cmp(UP[i], DP[j]);
}
double k = U[i].first + D[j].first, b = U[i].second + D[j].second;
if (c > 0) {
may = k * DP[j].first / DP[j].second + b;
++j;
}
else if (c == 0) {
may = k * DP[j].first / DP[j].second + b;
++i;
++j;
}
else {
may = k * UP[i].first / UP[i].second + b;
++i;
}
if (inf || (r > may)) {
inf = false;
r = may;
}
}
if (inf) {
r = U[0].second + D[0].second;
}
return r;
}