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≤1051≤k≤1081≤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​(0Di​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 n1){ 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 i1;in;i) a[i] read(); a[n1] d; l 1; r d; while (l r){ mid (lr) / 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≤1000≤K≤100。100% 的数据中2≤N≤100000, 0≤K≤100000。100% 的数据中0L≤10000000。实现代码#includeiostream #includecstdio #includealgorithm using namespace std; int sit[100005]; int L,N,K; inline bool check(int m){ int yK; int size0; for(int i1;iN;i) { if(y0) { break; } if(sit[i]-sizem){ sizesit[i]; } else{ sizesizem; i--; y--; } } if(y0) { return true; } return false; } int main() { cinLNK; int t0; while(tN) { cinsit[t]; t; } int H0,RL; int ans; while(HR) { int midH(R-H)/2; if(check(mid)) { ansmid; Rmid-1; } else { Hmid1; } } coutans; }P1182 数列分段 Section II题目描述对于给定的一个长度为 N 的正整数数列 A1∼N​现要将其分成 MM≤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≤105M≤NAi​108 答案不超过 109。实现代码#includeiostream using namespace std; int n,m; int a[100007]; int kl,kr1e91,km; int main() { cinnm; for(int i1;in;i) cina[i],klmax(kl,a[i]); while(klkr) { km(klkr)/2; int sum0,tot0; for(int i1;in;i) { if(suma[i]km)suma[i]; else suma[i],tot; } if(totm)krkm; else klkm1; } coutklendl; return 0; }P1163 银行贷款题目描述当一个人从银行贷款后在一段时间内他她将不得不每月偿还固定的分期付款。这个问题要求计算出贷款者向银行支付的利率。假设利率按月累计。输入格式三个用空格隔开的正整数。第一个整数表示贷款的原值 w0​第二个整数表示每月支付的分期付款金额 w第三个整数表示分期付款还清贷款所需的总月数 m。输出格式一个实数表示该贷款的月利率用百分数表示四舍五入精确到 0.1%。数据保证答案不超过 300.0%。输入输出样例输入 #1复制1000 100 12输出 #1复制2.9说明/提示数据保证1≤w0​,w≤231−11≤m≤3000。实现代码#includeiostream #includecstdio #includecstdlib 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(lr)/2,ur-l; double am; if(u0.0001) out(k); for(int i1;it;i) aa*(1k)-y; if(a0) solve(l,k); if(a0) solve(k,r); if(a0) out(k); } int main() { cinmyt; 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≤1051≤p≤1051≤ai​,bi​≤105。实现代码#include iostream using namespace std; int n; double p; double a[200000],b[200000]; double lbound0,rbound1e10; double sum0; int check(double ans){ double qp*ans; sum0; for(int i0;in;i){ if(a[i]*ansb[i]){ continue; } sum(a[i]*ans-b[i]); } return sumq; } int main(){ cinnp; for(int i0;in;i){ cina[i]b[i]; suma[i]; } if(sump){ cout-1.000000endl; return 0; } while(rbound-lbound1e-6){ double mid(lboundrbound)/2; if(check(mid)){ lboundmid; }else{ rboundmid; } } coutlboundendl; return 0; }