鹏鹏的算法博客

学习...学习..学习.



三分算法 && 模板题:曲线 + 传送带

顾名思义,所谓三分,就是像二分一样,在一个区间上三分。
等不等分无所谓,在某些情况下,不等分可能效率更高,但是全看数据。
二分要求函数是单调的,而三分要求是凸函数,有一个最值。
假设当前区间为[l, r],mid=(l+r)/2,midd=(mid+r)/2,这样就把区间三分了。设f(x)为计算的函数,如果f(mid)比f(midd)更接近最值,即求最小值时,f(mid)<f(midd);求最大值时,f(mid)>f(midd),那么最值点的位置肯定在[l, midd]之间,修改r=midd,否则就在[mid, r]之间,修改l=mid。最后找到的最值点就是l。


模板题1:曲线(一本通1439)

明明做作业的时候遇到了n个二次函数Si(x)= ax2 + bx + c,他突发奇想设计了一个新的函数F(x) = max(Si(x)), i = 1...n.
明明现在想求这个函数在[0,1000]的最小值,要求精确到小数点后四位四舍五入。

这题中原始l和r就是0和1000,要计算的函数就是F(x)。套模板即可。

#include <bits/stdc++.h>
using namespace std;

int n;
struct Func {
    int a, b, c;
    void read() { scanf("%d%d%d", &a, &b, &c); }
    double calc(double x) { return a * x * x + b * x + c; }
} s[10010];

double F(double x) {
    double max_value = -1 << 30;
    for (int i = 1; i <= n; ++i) { max_value = max(max_value, s[i].calc(x)); }
    return max_value;
}

int main() {

    int T;
    scanf("%d", &T);

    while (T--) {

        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) { s[i].read(); }

        double l = 0, r = 1000, mid, midmid;
        while (l + 1e-10 < r) {
            mid = (l + r) / 2;
            midmid = (mid + r) / 2;
            if (F(mid) < F(midmid)) r = midmid;
            else l = mid;
        }

        printf("%.4lf\n", F(l));

    }

    return 0;

}

模板题2:传送带(一本通1439)

在一个2维平面上有两条传送带,每一条传送带可以看成是一条线段。两条传送带分别为线段AB和线段CD。lxhgww在AB上的移动速度为P,在CD上的移动速度为Q,在平面上的移动速度R。现在lxhgww想从A点走到D点,他想知道最少需要走多长时间。

起点在A,终点在D,需要在AB和CD上分别找E和F,使得行走路线为A->E->F->D,第一段在传送带AB上,第二段是平面上,第三段在传送带CD上。找E和F可以分别用一个三分,先三分出E的位置并且固定下来,再去三分F的位置,就能求出来此时三分出来这个E点所需要的时间,然后调整E的区间,最终就可以找到使答案最小的E点了。

#include <bits/stdc++.h>
using namespace std;

const double EXP = 1e-10;

struct Point {
    double x, y;
    void read() { scanf("%lf%lf", &x, &y); }
    Point operator - (const Point &a) { return Point{x - a.x, y - a.y}; }
    Point operator + (const Point &a) { return Point{x + a.x, y + a.y}; }
    Point operator * (const double &e) { return Point{x * e, y * e}; }
    double distance(const Point &a) { return sqrt((x - a.x) * (x - a.x) + (y - a.y) * (y - a.y)); }
} a, b, c, d;

int p, q, r;

double calc(Point e, Point f) {
    return a.distance(e) / p + e.distance(f) / r + f.distance(d) / q;
}

double find(Point e) {
    double l = 0, r = 1, mid, midd;
    while (l + EXP < r) {
        mid = (l + r) / 2;
        midd = (mid + r) / 2;
        if (calc(e, c + (d - c) * mid) < calc(e, c + (d - c) * midd)) r = midd;
        else l = mid;
    }
    return calc(e, c + (d - c) * l);
}

int main() {

    a.read();
    b.read();
    c.read();
    d.read();
    scanf("%d%d%d", &p, &q, &r);

    double l = 0, r = 1, mid, midd;
    while (l + EXP < r) {
        mid = (l + r) / 2;
        midd = (mid + r) / 2;
        if (find(a + (b - a) * mid) < find(a + (b - a) * midd)) r = midd;
        else l = mid;
    }

    printf("%.2lf", find(a + (b - a) * l));

    return 0;

}