洛谷二分题单题解

王逗比666

本帖子用了Twilight6大佬的MarDisTextConverter源文本转换器将markdown文件转换而来，但是代码块和数学方面还是有一点显示问题，便于阅读我将.md文件也放到附件中，如果有小伙伴愿意看的话可以下载下来


[url=]洛谷二分题单题解.zip[/url]


题单来自洛谷 【算法1-6】二分查找与二分答案

P2249 【深基13.例1】查找
# 【深基13.例1】查找

题目描述

输入 $n$ 个不超过 $10^9$ 的单调不减的（就是后面的数字不小于前面的数字）非负整数 $a_1,a_2,\dots,a_{n}$，然后进行 $m$ 次询问。对于每次询问，给出一个整数 $q$，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 $-1$ 。

输入格式

第一行 $2$ 个整数 $n$ 和 $m$，表示数字个数和询问次数。

第二行 $n$ 个整数，表示这些待查询的数字。

第三行 $m$ 个整数，表示询问这些数字的编号，从 $1$ 开始编号。

输出格式

输出一行，$m$ 个整数，以空格隔开，表示答案。

样例 #1

样例输入 #1

1. 
   
2. 11 3
   
3. 1 3 3 3 5 7 9 11 13 15 15
   
4. 1 3 6
   

复制代码

样例输出 #1

1. 
   
2. 1 2 -1
   

复制代码

提示

数据保证，$1 \leq n \leq 10^6$，$0 \leq a_i,q \leq 10^9$，$1 \leq m \leq 10^5$

本题输入输出量较大，请使用较快的 IO 方式。

对于本题，只需要在分别输入数组$a$、$b$后分别查找$b$的每一个元素在$a$中出现的第一个位置即可，需要注意的是当没有找到时输出$-1$，当找到时要输出从$1$开始的编号，所以如果是从$a_0$开始写入数据则输出时要给结果$+1$

1. 
   
2. c++
   
3.     #include <iostream>
   
4. 
   
5.     using namespace std;
   
6. 
   
7.     int binary_search(int a[], int len, int x) {
   
8.         int l = -1, r = len;
   
9. 
   
10.         while(l + 1 != r) {
    
11.             int mid = (l + r) / 2;
    
12.             if(a[mid] == x)
    
13.                 r = mid;
    
14.             else if(a[mid] < x)
    
15.                 l = mid;
    
16.             else
    
17.                 r = mid;
    
18.         }
    
19.         if(a[r] == x)   return r;
    
20.         return -1;
    
21.     }
    
22. 
    
23.     int main(void) {
    
24.         int n, m;
    
25.         cin >> n >> m;
    
26.         int a[n], b[m];
    
27. 
    
28.         for(int i = 0; i < n; i++)
    
29.             cin >> a[i];
    
30.         for(int i = 0; i < m; i++) {
    
31.             cin >> b[i];
    
32.             int t = binary_search(a, n, b[i]);
    
33.             if(t == -1)
    
34.                 cout << t << " ";
    
35.             else
    
36.                 cout << t + 1 << " ";
    
37.         }
    
38. 
    
39.         cout << endl;
    
40. 
    
41.         return 0;
    
42.     }
    

复制代码

P1678 烦恼的高考志愿

# 烦恼的高考志愿

题目背景

计算机竞赛小组的神牛 V 神终于结束了高考，然而作为班长的他还不能闲下来，班主任老 t 给了他一个艰巨的任务：帮同学找出最合理的大学填报方案。可是 v 神太忙了，身后还有一群小姑娘等着和他约会，于是他想到了同为计算机竞赛小组的你，请你帮他完成这个艰巨的任务。

题目描述

现有 $m$ 所学校，每所学校预计分数线是 $a_i$。有 $n$ 位学生，估分分别为 $b_i$。

根据 $n$ 位学生的估分情况，分别给每位学生推荐一所学校，要求学校的预计分数线和学生的估分相差最小（可高可低，毕竟是估分嘛），这个最小值为不满意度。求所有学生不满意度和的最小值。

输入格式

第一行读入两个整数 $m,n$。$m$ 表示学校数，$n$ 表示学生数。

第二行共有 $m$ 个数，表示 $m$ 个学校的预计录取分数。第三行有 $n$ 个数，表示 $n$ 个学生的估分成绩。

输出格式

输出一行，为最小的不满度之和。

样例 #1

样例输入 #1

1. 
   
2. 4 3
   
3. 513 598 567 689
   
4. 500 600 550
   

复制代码

样例输出 #1

1. 
   
2. 32
   

复制代码

提示

数据范围：

对于 $30\%$ 的数据，$1\leq n,m\leq1000$，估分和录取线 $\leq10000$；

对于 $100\%$ 的数据，$1\leq n,m\leq100000$，估分和录取线 $\leq 1000000$ 且均为正整数。

本题可以用二分也可以用其他方法做，我看到题解上用二分的说他ac了，但是我复制了他的代码发现最后一个附加数据无法通过，我自己的代码也是最后一个数据超时，应该是想要ac就得用其他方法做

本题的思路是找到录取分数中与估分成绩分差最小的分数，求得每一个估分成绩的分差（也就是二者相减的绝对值）然后加起来就能得到所求的最小不满度之和。需要注意的是本题并没有说明输入的数据是有序的，所以在输入$m$个预计录取分数后要先对其排序才能使用二分

1. 
   
2. c++
   
3. [size=7][b]include <iostream>[/b][/size]
   
4. [size=7][b]include <algorithm> //直接用里面的sort函数[/b][/size]
   
5. 
   
6. using namespace std;
   
7. 
   
8. int search_binary(int a[], int b[], int len, int x, int i) {
   
9.     int l = 0, r = len - 1;  //左边界是a[]中的最低分(下标），又边界是最高分（下标）
   
10. 
    
11.     while(l + 1 != r) {
    
12.         int mid = (l + r) / 2;
    
13.         if(a[mid] <= x)
    
14.             l = mid;
    
15.         else
    
16.             r = mid;
    
17.     }
    
18. 
    
19.     return min(abs(a[l] - b[i]), abs(a[r] - b[i]));
    
20. 
    
21. }
    
22. 
    
23. int main(void) {
    
24.     int n, m, ans = 0;
    
25.     cin >> m >> n;
    
26.     int a[m], b[n];
    
27. 
    
28.     for(int i = 0; i < m; i++)
    
29.         cin >> a[i];
    
30.     sort(a, a + m);
    
31.     for(int i = 0; i < n; i++) {
    
32.         cin >> b[i];
    
33.         ans += search_binary(a, b, m, b[i], i);
    
34.     }
    
35. 
    
36.     cout << ans << endl;
    
37.    
    
38.     return 0;
    
39. }
    

复制代码

P1873 [COCI 2011/2012 #5] EKO / 砍树
[COCI 2011/2012 #5] EKO / 砍树

题目描述

伐木工人 Mirko 需要砍 $M$ 米长的木材。对 Mirko 来说这是很简单的工作，因为他有一个漂亮的新伐木机，可以如野火一般砍伐森林。不过，Mirko 只被允许砍伐一排树。

Mirko 的伐木机工作流程如下：Mirko 设置一个高度参数 $H$（米），伐木机升起一个巨大的锯片到高度 $H$，并锯掉所有树比 $H$ 高的部分（当然，树木不高于 $H$ 米的部分保持不变）。Mirko 就得到树木被锯下的部分。例如，如果一排树的高度分别为 $20,15,10$ 和 $17$，Mirko 把锯片升到 $15$ 米的高度，切割后树木剩下的高度将是 $15,15,10$ 和 $15$，而 Mirko 将从第 $1$ 棵树得到 $5$ 米，从第 $4$ 棵树得到 $2$ 米，共得到 $7$ 米木材。

Mirko 非常关注生态保护，所以他不会砍掉过多的木材。这也是他尽可能高地设定伐木机锯片的原因。请帮助 Mirko 找到伐木机锯片的最大的整数高度 $H$，使得他能得到的木材至少为 $M$ 米。换句话说，如果再升高 $1$ 米，他将得不到 $M$ 米木材。

输入格式

第 $1$ 行 $2$ 个整数 $N$ 和 $M$，$N$ 表示树木的数量，$M$ 表示需要的木材总长度。

第 $2$ 行 $N$ 个整数表示每棵树的高度。

输出格式

$1$ 个整数，表示锯片的最高高度。

样例 #1

样例输入 #1

1. 
   
2. 4 7
   
3. 20 15 10 17
   

复制代码

样例输出 #1

1. 
   
2. 15
   

复制代码

样例 #2

样例输入 #2

1. 
   
2. 5 20
   
3. 4 42 40 26 46
   

复制代码

样例输出 #2

1. 
   
2. 36
   

复制代码

提示

对于 $100\%$ 的测试数据，$1\le N\le10^6$，$1\le M\le2\times10^9$，树的高度 $<10^9$，所有树的高度总和 $>M$。

这道题的思路是从低到高枚举锯片的高度，如果锯片在某个高度砍树后的长度能够达到需要的总长度（大于等于），我们就将左边界移到当前高度，如果无法达到（小于），就将右边界移到当前高度

需要注意的地方是如果树的高度没有锯片高，则砍不下来任何的木材，所以我们应该将锯片的左边界设置为0，右边界设置为给出的树木中最高的树的高度

1. 
   
2. c++
   
3. [size=7][b]include <iostream>[/b][/size]
   
4. 
   
5. using namespace std;
   
6. 
   
7. long binary_search(long a[], long len, long x, long max) {
   
8.     long l = 0, r = max;
   
9.     while(l + 1 != r) {
   
10.         long t = 0;
    
11.         long mid = (l + r) / 2;
    
12.         for(long i = 0; i < len; i++) {
    
13.             if(a[i] > mid)
    
14.                 t += a[i] - mid;    //如果树比锯片高，就将砍下的木材的长度累加
    
15.         }
    
16.         if(t >= x)  //如果木材的长度达到了要求的长度设置左边界
    
17.             l = mid;
    
18.         else        //反之设置右边界
    
19.             r = mid;
    
20.     }
    
21. 
    
22.     return l;   //此时得到的左边界就是答案
    
23. }
    
24. 
    
25. int main(void) {
    
26.     long n, m;
    
27.     cin >> n >> m;
    
28.     long a[n];
    
29. 
    
30.     long maxn = 0;
    
31.     for(long i = 0; i < n; i++) {
    
32.         cin >> a[i];
    
33.         maxn = max(maxn, a[i]); //求得最高的树，作为右边界
    
34.     }
    
35. 
    
36.     long ans = binary_search(a, n, m, maxn);
    
37.     cout << ans << endl;
    
38.    
    
39.     return 0;
    
40. }
    

复制代码

P2440 木材加工
木材加工

题目背景

要保护环境

题目描述

木材厂有 $n$ 根原木，现在想把这些木头切割成 $k$ 段长度均为 $l$ 的小段木头（木头有可能有剩余）。

当然，我们希望得到的小段木头越长越好，请求出 $l$ 的最大值。

木头长度的单位是 $\text{cm}$，原木的长度都是正整数，我们要求切割得到的小段木头的长度也是正整数。

例如有两根原木长度分别为 $11$ 和 $21$，要求切割成等长的 $6$ 段，很明显能切割出来的小段木头长度最长为 $5$。

输入格式

第一行是两个正整数 $n,k$，分别表示原木的数量，需要得到的小段的数量。

接下来 $n$ 行，每行一个正整数 $L_i$，表示一根原木的长度。

输出格式

仅一行，即 $l$ 的最大值。

如果连 $\text{1cm}$ 长的小段都切不出来，输出 0。

样例 #1

样例输入 #1

1. 
   
2. 3 7
   
3. 232
   
4. 124
   
5. 456
   

复制代码

样例输出 #1

1. 
   
2. 114
   

复制代码

提示

数据规模与约定

对于 $100\%$ 的数据，有 $1\le n\le 10^5$，$1\le k\le 10^8$，$1\le L_i\le 10^8(i\in[1,n])$。

这道题和上一题有点像，我们还是通过二分枚举每一段的长度，如果在当前长度下可以切割出$k$段木头就将边界左移，反之右移。左边界为$0$，右边界为最高的木头的长度。同时本题并没有说明$L$是有序的，所以我们要先排序再二分

1. 
   
2. c++
   
3.     #include <iostream>
   
4.     #include <algorithm>
   
5. 
   
6.     using namespace std;
   
7. 
   
8.     long binary_search(long a[], long len, long max, long x) {
   
9.         long l = 0, r = max;
   
10. 
    
11.         while(l + 1 != r) {
    
12.             long t = 0;
    
13.             long mid = (l + r) / 2;
    
14.             for(int i = 0; i < len; i++) {
    
15.                 t += a[i] / mid;    //当前长度下能够切割成多少段
    
16.             }
    
17.             if(t >= x)
    
18.                 l = mid;    //当前长度足够切割出k段木头，边界左移
    
19.             else
    
20.                 r = mid;    //当前长度不够切割k段，边界右移
    
21.         }
    
22. 
    
23.         return l;   //l就是答案
    
24. 
    
25.     }
    
26. 
    
27.     int main(void) {
    
28.         long n, k, maxn = 0;;
    
29.         cin >> n >> k;
    
30. 
    
31.         long l[n];
    
32.         for(int i = 0; i < n; i++) {
    
33.             cin >> l[i];
    
34.             maxn = max(maxn, l[i]);
    
35.         }
    
36.             
    
37.         sort(l, l + n);
    
38. 
    
39.         long ans = binary_search(l, n, maxn, k);
    
40. 
    
41.         cout << ans << endl;
    
42.         
    
43.         return 0;
    
44.     }
    

复制代码

P2678 [NOIP2015 提高组] 跳石头
[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

1. 
   
2. 25 5 2
   
3. 2
   
4. 11
   
5. 14
   
6. 17
   
7. 21
   

复制代码

样例输出 #1

1. 
   
2. 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$。

>> 我们发现无论如何，跳跃距离的最大值都不会超过起点到终点的距离，所以本题的思路是从起点到终点之间二分，然后进行判断。如果起点和中间之间任意两个石头间的距离小于当前的距离，则需要移去一个石头，否则进行下一次判断。所有判断结束后如果要移走的石头数超过了可移走数$M$，则当前的距离不是最短跳跃距离的最大值，边界左移，否则边界右移

>> 需要注意的地方是起点到终点之间有$N$块石头，如果算上起点和终点的话实际上有$N + 2$块石头，另外二分的判断过程有些复杂，所以我们按照标准的二分写法写一个判断函数judge()来进行判断

1. 
   
2. c++
   
3. #include <iostream>
   
4. 
   
5. using namespace std;
   
6. 
   
7. bool judge(long a[], long len, long mid, long m) {
   
8.     int now = 0, cnt = 0;
   
9.     for(int i = 1; i <= len + 1; i++) { //在第一块石头和终点间进行判断
   
10.         if(a[i] - a[now] < mid)
    
11.             cnt++;
    
12.         else
    
13.             now = i;
    
14.     }
    
15.     return cnt <= m;    /[/i]
    
16.                             等价于:
    
17.                             if(cnt <= m)
    
18.                                 return true;
    
19.                             return false;
    
20.                         [i]/
    
21. }
    
22. 
    
23. long binary_search(long a[], long len, long distance, long m) {
    
24.     long l = 0, r = distance + 1;    //边界是起点和终点，避免特判将终点+1
    
25.     while(l + 1 != r) {
    
26.         long mid = (l + r) / 2;
    
27.         if(judge(a, len, mid, m))
    
28.             l = mid;
    
29.         else
    
30.             r = mid;
    
31.     }
    
32.    
    
33.     return l;   //此时左边界就是所求的最短跳跃距离的最大值
    
34. }
    
35. 
    
36. int main(void) {
    
37.     long l, n, m, ans;
    
38.     cin >> l >> n >> m;
    
39.    
    
40.     long a[n + 2];  //实际上有n + 2个石头，我们把a[0]作为起点，a[n + 1]作为终点
    
41.     a[0] = 0;
    
42.     a[n + 1] = l;
    
43.    
    
44.     for(long i = 1; i <= n; i++)
    
45.         cin >> a[i];
    
46.    
    
47.     ans = binary_search(a, n, l, m);
    
48.    
    
49.     cout << ans << endl;
    
50.    
    
51.     return 0;
    
52. }
    
53. 
    

复制代码

### P1182 数列分段 Section II
# 数列分段 Section II

题目描述

对于给定的一个长度为N的正整数数列 $A_{1\sim N}$，现要将其分成 $M$（$M\leq N$）段，并要求每段连续，且每段和的最大值最小。

关于最大值最小：

例如一数列 $4\ 2\ 4\ 5\ 1$ 要分成 $3$ 段。

将其如下分段：

$$[4\ 2][4\ 5][1]$$

第一段和为 $6$，第 $2$ 段和为 $9$，第 $3$ 段和为 $1$，和最大值为 $9$。

将其如下分段：

$$[4][2\ 4][5\ 1]$$

第一段和为 $4$，第 $2$ 段和为 $6$，第 $3$ 段和为 $6$，和最大值为 $6$。

并且无论如何分段，最大值不会小于 $6$。

所以可以得到要将数列 $4\ 2\ 4\ 5\ 1$ 要分成 $3$ 段，每段和的最大值最小为 $6$。

输入格式

第 $1$ 行包含两个正整数 $N,M$。  

第 $2$ 行包含 $N$ 个空格隔开的非负整数 $A_i$，含义如题目所述。

输出格式

一个正整数，即每段和最大值最小为多少。

样例 #1

样例输入 #1

1. 
   
2. 5 3
   
3. 4 2 4 5 1
   

复制代码

样例输出 #1

1. 
   
2. 6
   

复制代码

提示

对于 $20\%$ 的数据，$N\leq 10$。

对于 $40\%$ 的数据，$N\leq 1000$。

对于 $100\%$ 的数据，$1\leq N\leq 10^5$，$M\leq N$，$A_i < 10^8$， 答案不超过 $10^9$。

这道题看了大半天题解才知道怎么做

我们的思路是直接二分每段和的最大值，当按照这个最大值划分的段数超过指定的段数时就证明当前的值并非最大值，要继续往右搜索，相反如果段数没有达到指定段数就说明当前值超过了最大值，要往左搜索  
所以对于本题的左边界应该为将$n$个数分成$n$段时的每段和的最大值，即数列$A_n$的最大值，右边界为将$A_n$划分为一段时这段的长度，即$sumA_n$

另外本题所用的二分模板和上面几道题的二分模板不同，两个模板的思路是相同的，但是对于本题我们在求得$mid$后还需要根据是否满足$judge()$向终点的左边或右边搜索其实这个模板做上面的题也可以，只是我不喜欢这样写

1. 
   
2. c++
   
3.     #include <iostream>
   
4. 
   
5.     using namespace std;
   
6. 
   
7.     bool judge(long a[], long len, long x, long m) {
   
8.         long sum = 0, cnt = 1;
   
9.         /[i]
   
10.             这里我是这样理解的：任何情况下都至少会将数列分成1层
    
11.             所以我们直接从一层开始计算。
    
12.         [/i]/
    
13.         for(long i = 0; i < len; i++) {
    
14.             if(sum + a[i] <= x) { //当累加的值还没有超过最大值时，不算做一层，继续累加
    
15.                 sum += a[i];
    
16.             }
    
17.             else {
    
18.                 cnt ++;     //当累加值超过最大值时，已经达到了一层，层数+1
    
19.                 sum = a[i]; //从当前元素开始累加进行新一层的计算
    
20.             }
    
21.         }
    
22. 
    
23.         return cnt <= m;    //当cnt不超过m时说明当前的值达到了最大值，移动右边界
    
24. 
    
25.     }
    
26. 
    
27.     long binary_search(long a[], long len, long maxn,
    
28.     long sum, long m)
    
29.     {
    
30.         long l = maxn, r = sum;
    
31.         while(l <= r) {
    
32.             long mid = (l + r) / 2;
    
33.             if(judge(a, len, mid, m)) {
    
34.                 r = mid - 1;    //向左搜索
    
35.             }
    
36.             else
    
37.                 l = mid + 1;    //向右搜索
    
38.         }
    
39. 
    
40.         return l;   //此时左端点就是最大值
    
41.     }
    
42. 
    
43.     int main(void) {
    
44.         long n, m, maxn = 0, cnt = 0;
    
45.         cin >> n >> m;
    
46.         long a[n];
    
47.         for(long i = 0; i < n; i++) {
    
48.             cin >> a[i];
    
49.             maxn = max(maxn, a[i]); //左端点
    
50.             cnt += a[i];    //右端点
    
51.         }
    
52.         
    
53.         long ans = binary_search(a, n, maxn, cnt, m);
    
54. 
    
55.         cout << ans << endl;
    
56. 
    
57.         return 0;
    
58.     }
    

复制代码

P3743 kotori的设备
kotori的设备

题目背景

kotori 有 $n$ 个可同时使用的设备。

题目描述

第 $i$ 个设备每秒消耗 $a_i$ 个单位能量。能量的使用是连续的，也就是说能量不是某时刻突然消耗的，而是匀速消耗。也就是说，对于任意实数，在 $k$ 秒内消耗的能量均为 $k\times a_i$ 单位。在开始的时候第 $i$ 个设备里存储着 $b_i$ 个单位能量。

同时 kotori 又有一个可以给任意一个设备充电的充电宝，每秒可以给接通的设备充能 $p$ 个单位，充能也是连续的，不再赘述。你可以在任意时间给任意一个设备充能，从一个设备切换到另一个设备的时间忽略不计。

kotori 想把这些设备一起使用，直到其中有设备能量降为  $0$。所以 kotori 想知道，在充电器的作用下，她最多能将这些设备一起使用多久。

输入格式

第一行给出两个整数 $n,p$。

接下来 $n$ 行，每行表示一个设备，给出两个整数，分别是这个设备的 $a_i$ 和 $b_i$。

输出格式

如果 kotori 可以无限使用这些设备，输出 $-1$。

否则输出 kotori 在其中一个设备能量降为 $0$ 之前最多能使用多久。

设你的答案为 $a$，标准答案为 $b$，只有当 $a,b$ 满足
$\dfrac{|a-b|}{\max(1,b)} \leq 10^{-4}$ 的时候，你能得到本测试点的满分。

样例 #1

样例输入 #1

1. 
   
2. 2 1
   
3. 2 2
   
4. 2 1000
   

复制代码

样例输出 #1

1. 
   
2. 2.0000000000
   

复制代码

样例 #2

样例输入 #2

1. 
   
2. 1 100
   
3. 1 1
   

复制代码

样例输出 #2

1. 
   
2. -1
   

复制代码

样例 #3

样例输入 #3

1. 
   
2. 3 5
   
3. 4 3
   
4. 5 2
   
5. 6 1
   

复制代码

样例输出 #3

1. 
   
2. 0.5000000000
   

复制代码

提示

对于 $100\%$ 的数据，$1\leq n\leq 100000$，$1\leq p\leq 100000$，$1\leq a_i,b_i\leq100000$。

对于本题，我们可以理解为当k秒内消耗的电量$k\times a_i$超过了其本身的电量$b_i$，那么它在若干秒后就会用完电量，而我们要在使用所有设备的同时尽量让它们的使用时间长，也就是说要让第一个设备电量用完的情况尽可能晚的出现。我们可以让目前电量最少的设备接上充电宝，此时它的耗电就成了$k\times (a_i - p)$，当其它设备成为电量最少的设备时，我们将充电宝重新接到这个设备上
由于切换设备的时间是忽略不计的，我们可以当作以上行为是可以在瞬间内完成的，所以我们可以直接将它们累加到一起直接进行计算。那么我们就有了$n$个设备每秒消耗的电量$\sum_{i=1}^{n} a_i$

现在我们需要考虑如何通过程序来解决问题
我们可以二分查找这些设备的最大使用时间$x$，那么在x秒内我们通过充电宝一共可以供电$x \times p$，我们记作$q$。现在对每一个设备进行判断，如果第$i$个设备$x$秒内消耗的电量$a_i \times x$没有超过这个设备本身的电量$b_i$，就说明这个设备不需要充电，如果超过了这个电量我们就需要冲$a_i \times x - b_i$的电，最后所有设备一共要冲$\sum_{i=1}^{n} a_i \times x - b_i$的电，我们记作$sum$，如果$sum > q$说明当前的时间超过了最大使用时间，应该将右边界左移缩小范围；反之如果$sum \leq q$，说明当前时间没有超过最大使用时间，应该移动左边界继续查找。
另外当可以无限使用设备，即永远不会有设备没电时输出$-1$。我们可以进行特判，当可以无限使用设备时就说明所有设备每秒消耗的总电量永远不会超过充电宝每秒充入的电量，是否还记得上面的$\sum_{i=1}^{n} a_i$，我们将其记作$t$，那么当$t \leq p$时，输出$-1$

1. 
   
2. c++
   
3.     #include <iostream>
   
4. 
   
5.     using namespace std;
   
6. 
   
7.     bool judge(double x, double a[], double b[], double p,
   
8.         long len) {
   
9.             double sum = 0, q = x [/i] p;
   
10.             for(int i = 0 ; i < len; i++) {
    
11.                 if(a[i] [i] x <= b[i])
    
12.                     continue;   //不需要充电，判断下一个
    
13.                 else
    
14.                     sum += (a[i] [/i] x - b[i]);   //对需要充入的电量累加
    
15.             }
    
16. 
    
17.             return sum <= q;
    
18.             /[i]
    
19.                 如果充入的电量没有超过x秒内可以提供的电量
    
20.                 则当前结果可行
    
21.             [/i]/
    
22.         }
    
23. 
    
24.     double binary_search(double a[], double b[], long len,
    
25.         double p) {
    
26.             double l = 0, r = 1e10;
    
27.             /[i]
    
28.                 直接将左端点定义为0，右端点定义为足够大的值
    
29.             [/i]/
    
30. 
    
31.             /[i]
    
32.                  二分的时间复杂度是O(logn)，当执行一千次时精度绝对可以满足题目要求，可以省去对边界的判断
    
33.             [/i]/
    
34.             for(int i = 0; i < 1000; i++) {     
    
35.                 double mid = (l + r) / 2;
    
36.                 if(judge(mid, a, b, p, len))
    
37.                     l = mid;
    
38.                 else
    
39.                     r = mid;
    
40.             }
    
41. 
    
42.             return l;   //此时左端点就为答案
    
43.         }
    
44. 
    
45.     int main(void) {
    
46.         long n;
    
47.         double p, t = 0, ans = 0;
    
48.         cin >> n >> p;
    
49.         double a[n], b[n];
    
50.         for(int i = 0; i < n; i++) {
    
51.             cin >> a[i] >> b[i];
    
52.             t += a[i];  //对每秒消耗的电量进行累加
    
53.         }
    
54. 
    
55.         ans = binary_search(a, b, n, p);
    
56.         if(t <= p)   //特判
    
57.             ans = -1;
    
58.         cout << ans << endl;
    
59. 
    
60.         return 0;
    
61.     }
    

复制代码

*
P3853 [TJOI2007]路标设置
[TJOI2007]路标设置

题目背景

B 市和 T 市之间有一条长长的高速公路，这条公路的某些地方设有路标，但是大家都感觉路标设得太少了，相邻两个路标之间往往隔着相当长的一段距离。为了便于研究这个问题，我们把公路上相邻路标的最大距离定义为该公路的“空旷指数”。

题目描述

现在政府决定在公路上增设一些路标，使得公路的“空旷指数”最小。他们请求你设计一个程序计算能达到的最小值是多少。请注意，公路的起点和终点保证已设有路标，公路的长度为整数，并且原有路标和新设路标都必须距起点整数个单位距离。

输入格式

第 $1$ 行包括三个数 $L,N,K$，分别表示公路的长度，原有路标的数量，以及最多可增设的路标数量。


第 $2$ 行包括递增排列的 $N$ 个整数，分别表示原有的 $N$ 个路标的位置。路标的位置用距起点的距离表示，且一定位于区间 $[0,L]$ 内。

输出格式

输出 $1$ 行，包含一个整数，表示增设路标后能达到的最小“空旷指数”值。

样例 #1

样例输入 #1

1. 
   
2. 101 2 1
   
3. 0 101
   

复制代码

样例输出 #1

1. 
   
2. 51
   

复制代码

提示

公路原来只在起点和终点处有两个路标，现在允许新增一个路标，应该把新路标设在距起点 $50$ 或 $51$ 个单位距离处，这样能达到最小的空旷指数 $51$。

$50\%$ 的数据中，$2 \leq N \leq 100$，$0 \leq K \leq 100$。

$100\%$ 的数据中，$2 \leq N \leq 100000$, $0 \leq K \leq100000$。

$100\%$ 的数据中，$0 < L \leq 10000000$。

这道题是这个题单中唯一一道普及+/提高的题，不过要理解起来其实也很容易。实际上这道题和上面的[NOIP2015 提高组] 跳石头有点像，只是跳石头是在最短跳跃距离的最大值，本题是在求最小的“空旷指数”值

本题也是用通过二分查找能够满足要求的“空旷指数”（也就是二分答案，但是之前好像没有提到过），根据题目我们知道路标的位值一定在区间$[0, L]$内，所以我们可以将左右边界分别定义为$0$和输入的$L$
那么本题的思路就是判断每两个相邻路标之间的距离，如果距离大于我们给定的“空旷指数”$mid$，我们就在与第一个路标距离$mid$处添加一个路标，然后再次进行判断，知道两个路标之间距离小于$mid$，依次枚举后，我们就得到了在当前“空旷指数”下要添加的路标数$cnt$，当添加的路标数量超过了规定的最多可增设路标数量$k$，也就是$cnt > k$时，说明目前的答案大于最小空旷指数，我们应该移动左端点，相反当$cnt \geq k$时，我们移动右端点，判断结束后右端点就是我们的答案
本题最值的注意的地方时我们进行二分时如果$cnt > k$时，移动的是左端点，而最终答案是右端点，这与我们之前的题目相反。另外本题我们需要输入$n$个数，但是包含这些数的数组长度应该是$n + 2$，因为我我们需要用第一个元素存储起点，最后一个元素存储终点

1. 
   
2. c++
   
3.     #include <iostream>
   
4. 
   
5.     using namespace std;
   
6. 
   
7.     bool judge(int mid, int a[], int len, int k) {
   
8.         int cnt = 0;
   
9.         for(int i = 1; i <= len + 1; i++) {
   
10.             int dinstance = a[i] - a[i - 1];     //用来存放两个路标间的距离也就是“空旷指数”
    
11.             if(dinstance > mid) { //如果两个路标间的距离大于mid，增设路标
    
12.                 cnt++;
    
13.                 int t = dinstance - mid;
    
14.                 while(t > mid) {    //增设路标后继续判断，直到路标间的距离不超过mid
    
15.                     cnt++;
    
16.                     t -= mid;
    
17.                 }
    
18.             }
    
19.         }
    
20. 
    
21.         return cnt <= k;
    
22.     }
    
23. 
    
24.     int binary_search(int a[], int len, int finish, int k) {
    
25.         int l = 0, r = finish;   //参数finish即终点（准确的说是终点到起点的距离）
    
26.         while(l + 1 != r) {     //本题还是用这个二分模板，我个人很喜欢这个模板，能省去不少判断边界的麻烦
    
27.             int mid = (l + r) / 2;
    
28.             if(judge(mid, a, len, k))
    
29.                 r = mid;            //注意此时要移动右端点
    
30.             else
    
31.                 l = mid;
    
32.         }
    
33. 
    
34.         return r;       //答案也是右端点
    
35.     }
    
36. 
    
37.     int main(void) {
    
38.         int l, n, k;
    
39.         cin >> l >> n >> k;
    
40. 
    
41.         int a[n + 2];
    
42.         a[0] = 0;       //存放起点
    
43.         a[n + 1] = l;   //存放终点
    
44.         for(int i = 1; i <= n; i++)
    
45.             cin >> a[i];
    
46. 
    
47.         int ans = binary_search(a, n, l, k);
    
48. 
    
49.         cout << ans << endl;
    
50. 
    
51.         return 0;
    
52.     }
    

复制代码

实际上这个题单还有两道题，但是一道据说用二分只是一种特殊解法，实际上应该是双指针的模板题而且我还不会做，另一道题看不明白，所以这里就不写了看以后有没有心情去做，所以这个二分题单在这里就告一段落

Twilight6

感谢使用！！！ 爱你嗷~！

以后有机会继续更新， MarDisTextConverter 转换的瑕疵太多了

王逗比666

Twilight6 发表于 2023-4-23 11:45
感谢使用！！！ 爱你嗷~！

以后有机会继续更新， MarDisTextConverter 转换的瑕疵太多了

确实有一些内容能放到fishc上，等看到你更新我第一个就去用

Twilight6

王逗比666 发表于 2023-4-23 20:54
确实有一些内容能放到fishc上，等看到你更新我第一个就去用

嘿嘿，感谢哇，另外之前的在你说完没多久就修复完啦，在原帖更新了

其他功能以后有时间再慢慢来吧，最近也比较忙了TT.TT

王逗比666

Twilight6 发表于 2023-4-23 23:25
嘿嘿，感谢哇，另外之前的在你说完没多久就修复完啦，在原帖更新了

其他功能以后有时间再慢慢来吧 ...

看到了

Ewan-Ahiouy

                               
登录/注册后可看大图