洛谷-算法1-6-二分查找与二分答案2

P2440 木材加工

题目背景

要保护环境。

题目描述

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

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

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

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

输入格式

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

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

输出格式

仅一行，即 l 的最大值。

如果连 1cm 长的小段都切不出来，输出0。

输入输出样例

输入 #1复制

3 7 232 124 456

输出 #1复制

114

说明/提示

数据规模与约定

对于 100% 的数据，有 1≤n≤105，1≤k≤108，1≤Li​≤108(i∈[1,n])。

实现代码：

// #include <bits/stdc++.h> #include <queue> #include <stack> #include <cmath> #include <string> #include <cstdio> #include <iomanip> #include <cstring> #include <cstring> #include <iostream> #include <algorithm> using namespace std; long long n, k; long long a[1000005]; bool f(long long x) { long long ans = 0; for (int i = 1; i <= n; i++) { ans += a[i] / x; } return ans >= k; } int main() { cin >> n >> k; for (int i = 1; i <= n; i++) cin >> a[i]; long long l = 0, r = 100000001; long long mid; while (l + 1 < r) { mid = (l + r) / 2; if (f(mid)) l = mid; else r = mid; } cout << l << endl; return 0; }

P2678 [NOIP 2015 提高组] 跳石头

题目背景

NOIP2015 Day2T1

题目描述

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

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

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

输入格式

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

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

输出格式

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

输入输出样例

输入 #1复制

25 5 2 2 11 14 17 21

输出 #1复制

4

说明/提示

输入输出样例 1 说明

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

数据规模与约定

对于 20%的数据，0≤M≤N≤10。
对于 50% 的数据，0≤M≤N≤100。
对于 100% 的数据，0≤M≤N≤50000,1≤L≤109。

实现代码：

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #define maxn 500010 using namespace std; int d,n,m; int a[maxn]; int l,r,mid,ans; inline int read(){ int num = 0; char c; bool flag = false; while ((c = getchar()) == ' ' || c == '\n' || c == '\r'); if (c == '-') flag = true; else num = c - '0'; while (isdigit(c = getchar())) num = num * 10 + c - '0'; return (flag ? -1 : 1) * num; } bool judge(int x){ int tot = 0; int i = 0; int now = 0; while (i < n+1){ i++; if (a[i] - a[now] < x) tot++; else now = i; } if (tot > m) return false; else return true; } int main(){ d = read(); n = read(); m = read(); for (int i=1;i<=n;i++) a[i] = read(); a[n+1] = d; l = 1; r = d; while (l <= r){ mid = (l+r) / 2; if (judge(mid)){ ans = mid; l = mid + 1; } else r = mid - 1; } cout << ans << endl; return 0; }

P3853 [TJOI2007] 路标设置

题目背景

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

题目描述

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

输入格式

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

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

输出格式

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

输入输出样例

输入 #1复制

101 2 1 0 101

输出 #1复制

51

说明/提示

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

50% 的数据中，2≤N≤100，0≤K≤100。

100% 的数据中，2≤N≤100000, 0≤K≤100000。

100% 的数据中，0<L≤10000000。

实现代码：

#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int sit[100005]; int L,N,K; inline bool check(int m){ int y=K; int size=0; for(int i=1;i<N;i++) { if(y<0) { break; } if(sit[i]-size<=m){ size=sit[i]; } else{ size=size+m; i--; y--; } } if(y>=0) { return true; } return false; } int main() { cin>>L>>N>>K; int t=0; while(t<N) { cin>>sit[t]; t++; } int H=0,R=L; int ans; while(H<=R) { int mid=H+(R-H)/2; if(check(mid)) { ans=mid; R=mid-1; } else { H=mid+1; } } cout<<ans; }

P1182 数列分段 Section II

题目描述

对于给定的一个长度为 N 的正整数数列 A1∼N​，现要将其分成 M（M≤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 个空格隔开的非负整数 Ai​，含义如题目所述。

输出格式

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

输入输出样例

输入 #1复制

5 3 4 2 4 5 1

输出 #1复制

6

说明/提示

对于 20% 的数据，N≤10。

对于 40% 的数据，N≤1000。

对于 100% 的数据，1≤N≤105，M≤N，Ai​<108， 答案不超过 109。

实现代码：

#include<iostream> using namespace std; int n,m; int a[100007]; int kl,kr=1e9+1,km; int main() { cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i],kl=max(kl,a[i]); while(kl<kr) { km=(kl+kr)/2; int sum=0,tot=0; for(int i=1;i<=n;i++) { if(sum+a[i]<=km)sum+=a[i]; else sum=a[i],tot++; } if(tot<m)kr=km; else kl=km+1; } cout<<kl<<endl; return 0; }

P1163 银行贷款

题目描述

当一个人从银行贷款后，在一段时间内他（她）将不得不每月偿还固定的分期付款。这个问题要求计算出贷款者向银行支付的利率。假设利率按月累计。

输入格式

三个用空格隔开的正整数。

第一个整数表示贷款的原值 w0​，第二个整数表示每月支付的分期付款金额 w，第三个整数表示分期付款还清贷款所需的总月数 m。

输出格式

一个实数，表示该贷款的月利率（用百分数表示），四舍五入精确到 0.1%。

数据保证答案不超过 300.0%。

输入输出样例

输入 #1复制

1000 100 12

输出 #1复制

2.9

说明/提示

数据保证，1≤w0​,w≤231−1，1≤m≤3000。

实现代码：

#include<iostream> #include<cstdio> #include<cstdlib> using namespace std; double m,y,s; int t; int out(double k) { printf("%.1f",k*100); exit(0); } void solve(double l,double r) { double k=(l+r)/2,u=r-l; double a=m; if(u<0.0001) out(k); for(int i=1;i<=t;i++) a=a*(1+k)-y; if(a>0) solve(l,k); if(a<0) solve(k,r); if(a==0) out(k); } int main() { cin>>m>>y>>t; solve(0,5); }

P3743 小鸟的设备

题目描述

小鸟有 n 个可同时使用的设备，第 i 个设备每秒消耗 ai​ 个单位能量。能量的使用是连续的，也就是说能量不是某时刻突然消耗的，而是匀速消耗。也就是说，对于任意实数，在 k 秒内消耗的能量均为 k×ai​ 单位。在开始的时候第 i 个设备里存储着 bi​ 个单位能量。

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

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

输入格式

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

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

输出格式

如果小鸟可以无限使用这些设备，输出 −1。

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

设你的答案为 a，标准答案为 b，只有当 a,b 满足 max(1,b)∣a−b∣​≤10−4 的时候，你能得到本测试点的满分。

输入输出样例

输入 #1复制

2 1 2 2 2 1000

输出 #1复制

2.0000000000

输入 #2复制

1 100 1 1

输出 #2复制

-1

输入 #3复制

3 5 4 3 5 2 6 1

输出 #3复制

0.5000000000

说明/提示

对于 100% 的数据，1≤n≤105，1≤p≤105，1≤ai​,bi​≤105。

实现代码：

#include <iostream> using namespace std; int n; double p; double a[200000],b[200000]; double lbound=0,rbound=1e10; double sum=0; int check(double ans){ double q=p*ans; sum=0; for(int i=0;i<n;i++){ if(a[i]*ans<=b[i]){ continue; } sum+=(a[i]*ans-b[i]); } return sum<=q; } int main(){ cin>>n>>p; for(int i=0;i<n;i++){ cin>>a[i]>>b[i]; sum+=a[i]; } if(sum<=p){ cout<<-1.000000<<endl; return 0; } while(rbound-lbound>1e-6){ double mid=(lbound+rbound)/2; if(check(mid)){ lbound=mid; }else{ rbound=mid; } } cout<<lbound<<endl; return 0; }