【算法】二分——习题集

一.二分基础题

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

 给定一个按照升序排列的长度为 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的, 以后注意这种思路)。

 

上一篇:Spring运行报警告Cannot find template location: classpath:/templates/ (please add some templates or check


下一篇:C++ 代码模板:整数二分