一.二分基础题
给定一个按照升序排列的长度为 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 个方格区域中。
已知扫地机器人每分钟可以移动到左右相邻的方格中，并将该区域清扫干净。
请你编写一个程序，计算每台机器人的清扫路线，使得
- 它们最终都返回出发方格，
- 每个方格区域都至少被清扫一遍，
- 从机器人开始行动到最后一台机器人归位花费的时间最少。
注意多台机器人可以同时清扫同一方块区域，它们不会互相影响。
输出最少花费的时间。
在上图所示的例子中，最少花费时间是 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的， 以后注意这种思路）。