投稿
  1. 高性能架构探索首页
  2. C/C++

二分、三分基础知识

admin • • C/C++ • 阅读 158

二分

整数域上的二分

int l = 1, r = 1e9;
while (l <= r)
{
    int mid = l + r >> 1;
    if (check(mid))
        l = mid + 1;		//l始终代表合法答案的上一个
    else
        r = mid - 1;		//r始终代表不合法答案的下一个
}
cout << r << endl;			//保证了r的合法性

实数域上的二分

写法一：直接利用精度

double l = 0.0, r = 1e9;
double eps = 1e-9;
while (fabs(r - l) > eps)
{
    double mid = (r - l) / 2;
    if (check(mid))
        l = mid + 1;
    else
        r = mid - 1;
}
cout << r << endl;

写法二：利用cnt次数

如果\(cnt=10\)，那么精度应该为\(2^{10}-->0.0001\)，所以一般我们cnt取1000基本上就可以了

double l = 0.0, r = 1e9;
double eps = 1e-9;
int cnt = 1000;
while (cnt--)
{
    double mid = (r - l) / 2;
    if (check(mid))
        l = mid + 1;
    else
        r = mid - 1;
}
cout << r << endl;

三分

整数域上的三分

方法：大范围三分，小范围暴力枚举

int l = 1, r = 1e9;
while (r - 5 > l)
{
    int mid1 = l + r >> 1;
    int mid2 = mid1 + 1;
    if (check(mid1) <= check(mid2))
        l = mid - 1;
    else
        r = mid + 1;
}
int ans = -1;
for (int i = l; i <= r; ++i) // 假设求单峰最大值
{
    if (a[i] >= a[i - 1] && a[i] >= a[i + 1])
        ans = max(ans, a[i]);
}

实数域上的三分

double l=0.0,r =1e9;
double eps =1e-9;
while (fabs(r-l)>eps)
{
    double mid = (l+r)/2;
    double mid1 = mid-eps;
    double mid2 = mid+eps;
    // double mid1 = l+(r-l)/3;
    // double mid2 = r-(r-l)/3;
    if (check(mid1) <= check(mid2))
        l = mid - 1;
    else
        r = mid + 1;
}

double l = 0.0, r = 1e9;
double eps = 1e-9;
int cnt = 1000;
while (cnt--)
{
    double mid = (l + r) / 2;
    double mid1 = mid - eps;
    double mid2 = mid + eps;
    // double mid1 = l+(r-l)/3;
    // double mid2 = r-(r-l)/3;
    if (check(mid1) <= check(mid2))
        l = mid - 1;
    else
        r = mid + 1;
}

【模板】三分法

题目描述

如题，给出一个 \(N\) 次函数，保证在范围 \([l, r]\) 内存在一点 \(x\)，使得 \([l, x]\) 上单调增，\([x, r]\) 上单调减。试求出 \(x\) 的值。

输入格式

第一行一次包含一个正整数 \(N\) 和两个实数 \(l, r\)，含义如题目描述所示。

第二行包含 \(N + 1\) 个实数，从高到低依次表示该 \(N\) 次函数各项的系数。

输出格式

输出为一行，包含一个实数，即为 \(x\) 的值。若你的答案与标准答案的相对或绝对误差不超过 \(10^{-5}\) 则算正确。

样例 #1

样例输入 #1

3 -0.9981 0.5
1 -3 -3 1

样例输出 #1

-0.41421

提示

对于 \(100\%\) 的数据，\(6 \le N \le 13\)，函数系数均在 \([-100,100]\) 内且至多 \(15\) 位小数，\(|l|,|r|\leq 10\) 且至多 \(15\) 位小数。\(l\leq r\)。

【样例解释】

二分、三分基础知识

如图所示，红色段即为该函数 \(f(x) = x^3 - 3 x^2 - 3x + 1\) 在区间 \([-0.9981, 0.5]\) 上的图像。

当 \(x = -0.41421\) 时图像位于最高点，故此时函数在 \([l, x]\) 上单调增，\([x, r]\) 上单调减，故 \(x = -0.41421\)，输出 \(-0.41421\)。

#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define all(x) (x).begin(), (x).end()
#define endl '\n'
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 2e5 + 10;
double a[20];
int n;
double f(double x)
{
    double ans = 0;
    for (int i = 0; i <= n; ++i)
    {
        ans += a[i] * pow(x, n - i);
    }
    return ans;
}
int main(void)
{
    Zeoy;
    int t = 1;
    // cin >> t;
    while (t--)
    {
        double l, r;
        cin >> n >> l >> r;
        for (int i = 0; i <= n; ++i)
            cin >> a[i];
        int cnt = 1000;
        while (cnt--)
        {
            double mid = (l + r) / 2;
            double mid1 = mid - eps;
            double mid2 = mid + eps;
            if (f(mid1) <= f(mid2))
            {
                l = mid;
            }
            else
                r = mid;
        }
        cout << r << endl;
    }
    return 0;
}

二分交互

猜数（IO交互版）

题目描述

评测机会在区间 \([1,10^9]\) 中选择一个整数，你应该写一个代码来猜测它。你最多可以问评测机 \(50\) 个问题。

对于每一次询问，你可以向评测机询问区间 \([1,10^9]\) 中的一个整数，评测机会返回:

  • 0，如果它为答案（即评测机所选的数字），且程序应该在此之后停止询问。
  • -1，如果它小于答案。
  • 1，如果它大于答案。

每次询问，你需要向标准输出输出一个 \([1,10^9]\) 中的整数，然后清空缓冲区。

特别的，对于 C++ 语言，在输出换行时如果你使用 std::endl 而不是 '\n'，也可以自动刷新缓冲区。

然后你需要从标准输入中输入一个整数，代表评测机返回的结果。

输入格式

输出格式

提示

数据规模与约定

设 \(n\) 为答案。

  • 对于 \(50\%\) 的数据，保证 \(n \leq 51\)。
  • 对于 \(100\%\) 的数据，保证 \(1 \leq n \leq 10^9\)。

本题交互库。

#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 2e5 + 10;
int main(void)
{
    Zeoy;
    int t = 1;
    //cin >> t;
    while (t--)
    {
        int l=1,r=1e9;
        while (l<=r)
        {
            int mid = l+r >> 1;
            cout << mid << endl;
            int check;
            cin >> check;
            if (!check)
                break;
            else if (check==1)
            {
                r = mid - 1;
            }
            else    
                l = mid+1;
        }
    }
    return 0;
}

二分答案

关键词：最大值最小化/最小值最大化

进击的奶牛

题目描述

Farmer John 建造了一个有 \(N\)(\(2\) \(\le\) \(N\) \(\le\) \(100000\)) 个隔间的牛棚，这些隔间分布在一条直线上，坐标是 \(x_1\) ,...,\(x_N\)
(0 \(\le\) \(x_i\) \(\le\) \(1000000000\))。

他的 \(C\)(\(2\) \(\le\) \(C\) \(\le\) \(N\)) 头牛不满于隔间的位置分布，它们为牛棚里其他的牛的存在而愤怒。为了防止牛之间的互相打斗，Farmer John 想把这些牛安置在指定的隔间，所有牛中相邻两头的最近距离越大越好。那么，这个最大的最近距离是多少呢？

输入格式

第 \(1\) 行：两个用空格隔开的数字 \(N\) 和 \(C\)。

第 \(2\) ~ \(N+1\) 行：每行一个整数，表示每个隔间的坐标。

输出格式

输出只有一行，即相邻两头牛最大的最近距离。

样例 #1

样例输入 #1

5 3
1
2
8
4
9

样例输出 #1

3

#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define all(x) (x).begin(), (x).end()
#define endl '\n'
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 1e5 + 10;
int n, c;
ll a[N];
bool check(int mid)
{
    ll pre = a[1];
    int cnt = 0;
    for (int i = 2; i <= n; ++i)
    {
        if (a[i] - pre >= mid)
            pre = a[i];
        else
            cnt++;
    }
    if (cnt <= n - c)
        return 1;
    else
        return 0;
}
int main(void)
{
    Zeoy;
    int t = 1;
    // cin >> t;
    while (t--)
    {
        cin >> n >> c;
        for (int i = 1; i <= n; ++i)
            cin >> a[i];
        sort(a + 1, a + 1 + n);
        int l = 1, r = a[n] - a[1];
        while (l <= r)
        {
            int mid = l + r >> 1;
            if (check(mid))
                l = mid + 1;
            else
                r = mid - 1;
        }
        cout << r << endl;
    }
    return 0;
}

[NOIP2015 提高组] 跳石头

题目背景

一年一度的“跳石头”比赛又要开始了!

题目描述

这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 \(N\) 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。

为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 \(M\) 块岩石（不能移走起点和终点的岩石）。

输入格式

第一行包含三个整数 \(L,N,M\)，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证 \(L \geq 1\) 且 \(N \geq M \geq 0\)。

接下来 \(N\) 行，每行一个整数，第 \(i\) 行的整数 \(D_i( 0 < D_i < L)\)， 表示第 \(i\) 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。

输出格式

一个整数，即最短跳跃距离的最大值。

样例 #1

样例输入 #1

25 5 2 
2
11
14
17 
21

样例输出 #1

4

提示

输入输出样例 1 说明

将与起点距离为 \(2\)和 \(14\) 的两个岩石移走后,最短的跳跃距离为 \(4\)(从与起点距离 \(17\) 的岩石跳到距离 \(21\) 的岩石,或者从距离 \(21\) 的岩石跳到终点)。

数据规模与约定

对于 \(20\%\)的数据，\(0 \le M \le N \le 10\)。
对于 \(50\%\) 的数据，\(0 \le M \le N \le 100\)。
对于 \(100\%\)的数据，\(0 \le M \le N \le 50000,1 \le L
\le 10^9\)。

思路：我们发现对于最短跳跃距离来说，距离越大说明我们需要移走的石头越多，那么我们会发现随着最短跳跃距离从大到小变化中，会从答案的不合法变到合法，说明我们可以二分答案，我们直接二分最短跳跃距离，知道找到合法答案和不合法答案的临界点，这个点就是最短跳跃距离的最大值，那么最重要的就是如何写check函数，假设我们现在二分到的最短跳跃距离为K，我们就去找为了满足这个最短跳跃距离，我们需要移走多少石头，如果移走的石头>M，说明答案是不合法的，当然我们需要注意，起点和终点的石头不能移走，所以在倒数第一块石头处需要和终点进行特判

#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define all(x) (x).begin(), (x).end()
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 5e4 + 10;
ll a[N];
int len, m, n;
bool check(int mid)
{
    int cnt = 0;
    int pre = 0;                // 记录前一块没被移走的石头的位置
    for (int i = 1; i <= n; ++i)
    {
        if (a[i] - pre < mid)   // 如果两块石头之间的距离小于最短跳跃距离。说明需要移走
            cnt++;
        else
            pre = a[i];         // 如果两块石头之间的距离大于等于最短跳跃距离，说明该石头不用移走，但是我们需要更新前一块没被移走的石头的位置
    }
    if (len - a[n] < mid)       // 对终点和倒数第一块石头特判
        cnt++;
    if (cnt > m)
        return 0;
    else
        return 1;
}
int main(void)
{
    Zeoy;
    int t = 1;
    // cin >> t;
    while (t--)
    {
        cin >> len >> n >> m;
        for (int i = 1; i <= n; ++i)
        {
            cin >> a[i];
        }
        int l = 0, r = len;
        while (l <= r)
        {
            int mid = l + r >> 1;
            if (check(mid))
                l = mid + 1;
            else
                r = mid - 1;
        }
        cout << r << endl;
    }
    return 0;
}

原文链接: https://www.cnblogs.com/Zeoy-kkk/p/17034142.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍

    二分、三分基础知识

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/310680

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
adminadmin
0 0
上一篇 2023年2月16日 上午11:40
下一篇 2023年2月16日 上午11:41

相关推荐