三分アルゴリズム初見(バレンタイン個人専用場)

2550 ワード

三分アルゴリズムの前人の述備は、私たちは見て勉強すればいいだけです.
いくつかの高品質のブログ
https://blog.csdn.net/Littlewhite520/article/details/70144763
https://blog.csdn.net/pi9nc/article/details/9666627
区間最大値の検索

int Three_Search(int n)
{
    int L = 1;
    int R = n;
    int mid, mmid; // mid   R   
    while (L < R - 1)
    {
        // cout << L << " " << R<< endl;
        mid = (L + R) >> 1;
        mmid = (mid + R) >> 1;
        if (a[mid] > a[mmid])
            R = mmid;
        else
            L = mid;
    }
    return a[L] < a[R] ? L : R;
}

区間最小値の検索

int Three_Search(int n)
{
    int L = 1;
    int R = n;
    int mid, mmid; // mid   R   
    while (L < R - 1)
    {
        mid = (L + R) >> 1;
        mmid = (mid + R) >> 1;
        if (a[mid] < a[mmid])
            R = mmid;
        else
            L = mid;
    }
    return a[L] < a[R] ? L : R;
}

2020牛客第5回B題
タイトルリンクhttps://ac.nowcoder.com/acm/contest/3006/B
この問題は三分アルゴリズムを用いて凸関数の最大値を探す例である.
コードを添付するのは問題解とほぼ同じです

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define IO                       \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    // cout.tie(0);
using namespace std;
typedef long long LL;
const int maxn = 100000 + 10;
struct p
{
    int x, y;
} p[maxn];
int n;
double dist(double x)
{
    double max = 0;
    for (int i = 1; i <= n; i++)
    {
        double t = sqrt(p[i].y * p[i].y + (p[i].x - x) * (p[i].x - x));
        if (t > max)
            max = t;
    }
    return max;
}
double Three_Search(double L, double R)
{
    int i;
    double mid, mmid;
    for (i = 0; i < 100; i++)  //                    
    {
        mid = L + (R - L) / 2;
        mmid = mid + (R - mid) / 2;
        if (dist(mid) > dist(mmid)) //      
            L = mid;
        else
            R = mmid;
    }
    return mid;
}
int main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
#endif
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &p[i].x, &p[i].y);
    double max = Three_Search(-10000, 10000); //     
    printf("%.4lf
", dist(max));
    return 0;
}

洛谷P 2731騎馬修柵オーラ経路

【アルゴリズム——Python実装】最小インデックススタック、最小スタックの最適化