一.二分基础题

整数二分—— 有序数列 查询数字

 给定一个按照升序排列的长度为 nn 的整数数组，以及 qq 个查询。

对于每个查询，返回一个元素 kk 的起始位置和终止位置（位置从 00 开始计数）。

如果数组中不存在该元素，则返回 -1 -1。

输入格式

第一行包含整数 nn 和 qq，表示数组长度和询问个数。

第二行包含 nn 个整数（均在 1∼100001∼10000 范围内），表示完整数组。

接下来 qq 行，每行包含一个整数 kk，表示一个询问元素。

输出格式

共 qq 行，每行包含两个整数，表示所求元素的起始位置和终止位置。

如果数组中不存在该元素，则返回 -1 -1。

数据范围

1≤n≤1000001≤n≤100000
1≤q≤100001≤q≤10000
1≤k≤100001≤k≤10000

输入样例：

6 3
1 2 2 3 3 4
3
4
5

输出样例：

3 4
5 5
-1 -1

代码：

#include<iostream>
using namespace std;
const int N = 100020;
int q[N];

int main()
{
    int n, pp;
    cin >> n >> pp;
    for (int i = 0; i < n; i++) cin >> q[i];
    while (pp--)
    {
        int k;
        cin >> k;
        int l = 0, r = n - 1;
        while (l < r)
        {
            int mid = l + r >> 1;    //放while循环里面
            if (q[mid] >= k) r = mid;
            else l = mid + 1;
        }
        if (q[l] != k)cout << "-1 -1" << endl;
        else
        {
            cout << l << " ";
            l = 0, r = n - 1;
            while (l < r)
            {
                int mid = l + r + 1 >> 1;   //放while循环里面
                if (q[mid] <= k) l = mid;
                else r = mid - 1;
            }
            cout << l << endl;
        }
    }
    return 0;
}

实数二分——算方程的根

给定一个浮点数 nn，求它的三次方根。

输入格式

共一行，包含一个浮点数 nn。

输出格式

共一行，包含一个浮点数，表示问题的解。

注意，结果保留 66 位小数。

数据范围

−10000≤n≤10000−10000≤n≤10000

输入样例：

1000.00

输出样例：

10.000000

代码：

#include<iostream>
using namespace std;
int main()
{
	double n;
	cin >> n;

	double l = - 100 , r = 100 ;
	while ((r - l) > 1e-8)
	{
		double ans = (l + r)/2;
		if (ans * ans * ans > n) r = ans;
		else l = ans;
	}
	printf("%.6lf", l );
}

二. 二分结合贪心

题目一

题目描述

一年一度的「跳石头」比赛又要开始了！

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

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

输入描述

输入文件第一行包含三个整数 L，N，ML，N，M，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。

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

其中，0 \leq M \leq N \leq 5 \times 10^4，1 \leq L \leq 10^90≤M≤N≤5×104，1≤L≤109。

输出描述

输出只包含一个整数，即最短跳跃距离的最大值。

样例输入

25 5 2
2
11
14
17
21

样例输出

4

代码：

//2022-01-15
//二分——贪心
#include<iostream>
using namespace std;
const int N = 5E4 + 20;
int ll, m, n;
int q[N];
bool check(int dis)  //判断当mid是最小跳跃距离，m是2 是否成立
{
    /*********以下内容为搬运正确答案，当时想不出！！！是贪心的思路****************/
    int stand = 0;  //我现在站的位置
    int sum = 0;    //已经搬走的石头数目
    //模拟我走石头的过程 走一遍即可
    for (int i = 0; i < n; i++)
    {
        if ((q[i] - stand) < dis) sum++;
        else stand = q[i];
    }
    if (sum <= m)return true;
    else return false;
}
int main()
{
    cin >> ll >> n >> m;

    for (int i = 0; i < n; i++)cin >> q[i];
    int l = 1, r = ll;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    //    printf("mid=%d  check=%d\n", mid, check(mid));
    }
    cout << l << endl;
    return 0;
}

  题目二

小明公司的办公区有一条长长的走廊，由 NN 个方格区域组成，如下图所示。

走廊内部署了 KK 台扫地机器人，其中第 ii 台在第 AiAi 个方格区域中。

已知扫地机器人每分钟可以移动到左右相邻的方格中，并将该区域清扫干净。

请你编写一个程序，计算每台机器人的清扫路线，使得

1. 它们最终都返回出发方格，
2. 每个方格区域都至少被清扫一遍，
3. 从机器人开始行动到最后一台机器人归位花费的时间最少。

注意多台机器人可以同时清扫同一方块区域，它们不会互相影响。

输出最少花费的时间。

在上图所示的例子中，最少花费时间是 66。

第一台路线：2−1−2−3−4−3−22−1−2−3−4−3−2，清扫了 1、2、3、41、2、3、4 号区域。

第二台路线 5−6−7−6−55−6−7−6−5，清扫了 5、6、75、6、7。

第三台路线 10−9−8−9−1010−9−8−9−10，清扫了 8、98、9 和 1010。

输入格式

第一行包含两个整数 NN 和 KK。

接下来 KK 行，每行一个整数 AiAi。

输出格式

输出一个整数表示答案。

数据范围

1≤K<N≤105 ，1≤K<N≤105,
1≤Ai≤N1≤Ai≤N

输入样例：

10 3
5
2
10

代码：

#include <iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, k;  //一共n个格子  k个机器人
int q[N];
bool check(int x)    //给一个最大花费时间 (假设是6)   难点在于：如何判断
{
    int now = 0; //目前已经ok的格子数目  最终与n比较大小
    for (int i = 0; i < k; i++)
    {
        if (now + x / 2 >= q[i])  //至少可以走到左边界
        {
           
            if (now < q[i] - 1)    //需要再往左扫
            {
                now = q[i] + (x - (q[i] - now - 1) * 2) / 2;
      
            }
            else  //不需要往左边扫
            {
                now = q[i] + x / 2;
            }
        //   printf("33 %d %d\n", x, now);
        }
        else    //花最大花费时间都走不到左边界
            return 0;
    }
    if (now >= n)return 1;
    else return 0;

}
int main()
{
    cin >> n >> k;
    for (int i = 0; i < k; i++)cin >> q[i];
    sort(q, q + k); 
    int l = 0, r = n;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid))r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
    return 0;
}

总结：

1. 目标序列一份为二问题（即能否用二分）

按题意 其实只有x为偶数才是答案，但是在函数check（）中判定now>n 即可，这样就把目标序列一分为二，即目标值右侧都算是正解。

2. check()函数中用了贪心思想， 即模拟走石头题 只要考虑当下走完即可（主要的写法还是cp的， 以后注意这种思路）。