1.11编程基础之二分查找(10题)

1、.1: 查找最接近的元素描述在一个非降序列中，查找与给定值最接近的元素。输入第一行包含一个整数n ，为非降序列长度。1 = n = 100000。第二行包含n 个整数，为非降序列各元素。所有元素的大小均在0-1,000,000,000之间。第三行包含一个整数m ，为要询问的给定值个数。1 = m 0, f(2.4) 0且方程 f(x) = 0在区间 1.5,2.4有且只有一个根，请用二分法求出该根。输入无。输出该方程在区间 1.5,2.4中的根。要求四舍五入到小数点后6 位。样例输入无样例输出不提供.03: 切分矩形组? 查看? 提交? 统计? 提问总时间限制 :1000ms内存限制 :655

2、36kB描述给定若干个平行于坐标轴的互不重叠的矩形， 矩形的顶点都是整点。 要求画一根平行于 y 轴的直线 x=k （k 是整数 ) ，使得这些矩形落在直线两边面积之差最小。注意：若直线穿过一个矩形，将会把它切成两个部分，分属左右两侧。输入第一行是整数n ，表示有 n 个矩形 (0 n = 10000)。接下来是n 行，每行表示一个矩形。 每行有 4 个整数 left,top,w,h分别代表矩形左上角横坐标， 矩形左上角纵坐标，矩形宽度，矩形高度。 0 = left,top= 1000000, 0 = w,h = 100000。输出输出使得直线 x= k 两边所包含的矩形面积差最小的 k 。如

3、果有多条直线满足要求，输出最小的 k 。样例输入21 1 100 1001000 1 100 100样例输出101.4: 网线主管描述仙境的居民们决定举办一场程序设计区域赛。 裁判委员会完全由自愿组成， 他们承诺要组织一次史上最公正的比赛。 他们决定将选手的电脑用星形拓扑结构连接在一起， 即将它们全部连到一个单一的中心服务器。 为了组织这个完全公正的比赛，裁判委员会主席提出要将所有选手的电脑等距离地围绕在服务器周围放置。为购买网线， 裁判委员会联系了当地的一个网络解决方案提供商，要求能够提供一定数量的等长网线。 裁判委员会希望网线越长越好， 这样选手们之间的距离可以尽可能远一些。该公司的网线主

4、管承接了这个任务。他知道库存中每条网线的长度（精确到厘米），并且只要告诉他所需的网线长度（精确到厘米），他都能够完成对网线的切割工作。但是，这次，所需的网线长度并不知道， 这让网线主管不知所措。你需要编写一个程序， 帮助网线主管确定一个最长的网线长度， 并且按此长度对库存中的网线进行切割，能够得到指定数量的网线。输入第一行包含两个整数N 和 K ，以单个空格隔开。N（ 1 = N = 10000）是库存中的网线数，K（ 1 = K = 10000）是需要的网线数量。接下来 N 行，每行一个数，为库存中每条网线的长度（单位：米）。所有网线的长度至少 1m ，至多 100km 。输入中的所有长度都

5、精确到厘米，即保留到小数点后两位。输出网线主管能够从库存的网线中切出指定数量的网线的最长长度（单位：米）。必须精确到厘米，即保留到小数点后两位。若无法得到长度至少为 1cm 的指定数量的网线， 则必须输出 “0.00 ”（不包含引号）。样例输入4 118.027.434.575.39样例输出2.00来源Northeastern Europe 2001.5: 派描述我的生日要到了！ 根据习俗，我需要将一些派分给大家。 我有 N 个不同口味、不同大小的派。有 F 个朋友会来参加我的派对，每个人会拿到一块派（必须一个派的一块，不能由几个派的小块拼成；可以是一整个派）。我的朋友们都特别小气， 如果有人

6、拿到更大的一块， 就会开始抱怨。 因此所有人拿到的派是同样大小的 （但不需要是同样形状的） ，虽然这样有些派会被浪费，但总比搞砸整个派对好。当然， 我也要给自己留一块，而这一块也要和其他人的同样大小。请问我们每个人拿到的派最大是多少？每个派都是一个高为1 ，半径不等的圆柱体。输入第一行包含两个正整数N 和 F， 1 N, F 10 000 ，表示派的数量和朋友的数量。第二行包含N 个 1 到 10000之间的整数，表示每个派的半径。输出输出每个人能得到的最大的派的体积，精确到小数点后三位。样例输入3 34 3 3样例输出25.133.6: 月度开销描述农夫约翰是一个精明的会计师。他意识到自己可

7、能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来N (1 N 100,000) 天里每天需要的开销。约翰打算为连续的M (1 M N) 个财政周期创建预算案，他把一个财政周期命名为 fajo 月。每个 fajo 月包含一天或连续的多天，每天被恰好包含在一个fajo 月里。约翰的目标是合理安排每个 fajo 月包含的天数，使得开销最多的 fajo 月的开销尽可能少。输入第一行包含两个整数N,M ，用单个空格隔开。接下来 N 行，每行包含一个 1 到 10000 之间的整数，按顺序给出接下来 N 天里每天的开销。输出一个整数，即最大月度开销的最小值。样例输入7 5100400300100

8、500101400样例输出500提示若约翰将前两天作为一个月， 第三、四两天作为一个月， 最后三天作为一个月，则最大月度开销为 500 。其他任何分配方案都会比这个值更大。.07: 和为给定数? 查看? 提交? 统计? 提问总时间限制 :1000ms内存限制 :65536kB描述给出若干个整数，询问其中是否有一对数的和等于给定的数。输入共三行：第一行是整数n(0 n = 100,000)，表示有 n 个整数。第二行是n 个整数。整数的范围是在0 到 108之间。第三行是一个整数m （ 0 = m = 230)，表示需要得到的和。输出若存在和为m 的数对，输出两个整数，小的在前，大的在后，中间用

9、单个空格隔开。 若有多个数对满足条件， 选择数对中较小的数更小的。 若找不到符合要求的数对，输出一行 No 。样例输入42 5 1 46样例输出1 5.08: 不重复地输出数? 查看? 提交? 统计? 提问总时间限制 :1000ms内存限制 :65536kB描述输入 n 个数，从小到大将它们输出，重复的数只输出一次。保证不同的数不超过 500 个。输入第一行是一个整数n 。 1 = n = 100000。之后 n 行，每行一个整数。整数大小在int 范围内。输出一行，从小到大不重复地输出这些数，相邻两个数之间用单个空格隔开。样例输入52 4 4 5 1样例输出1 2 4 5.9: 膨胀的木棍描

10、述当长度为L 的一根细木棍的温度升高n 度，它会膨胀到新的长度L=(1+n*C)*L，其中 C 是热膨胀系数。当一根细木棍被嵌在两堵墙之间被加热， 它将膨胀形成弓形的弧， 而这个弓形的弦恰好是未加热前木棍的原始位置。你的任务是计算木棍中心的偏移距离。输入三个非负实数：木棍初始长度（单位：毫米），温度变化（单位：度），以及材料的热膨胀系数。保证木棍不会膨胀到超过原始长度的1.5 倍。输出木棍中心的偏移距离（单位：毫米），保留到小数点后第三位。样例输入1000 100 0.0001样例输出61.329.10: 河中跳房子描述每年奶牛们都要举办各种特殊版本的跳房子比赛，包括在河里从一个岩石跳到另一个

11、岩石。 这项激动人心的活动在一条长长的笔直河道中进行，在起点和离起点 L 远 (1 L 1,000,000,000) 的终点处均有一个岩石。 在起点和终点之间，有 N (0 N 50,000) 个岩石，每个岩石与起点的距离分别为Di (0 Di L)。在比赛过程中， 奶牛轮流从起点出发， 尝试到达终点， 每一步只能从一个岩石跳到另一个岩石。当然，实力不济的奶牛是没有办法完成目标的。农夫约翰为他的奶牛们感到自豪并且年年都观看了这项比赛。但随着时间的推移，看着其他农夫的胆小奶牛们在相距很近的岩石之间缓慢前行，他感到非常厌烦。他计划移走一些岩石，使得从起点到终点的过程中，最短的跳跃距离最长。他可以移走除起点和终点外的至多M (0 M N) 个岩石。请帮助约翰确定移走这些岩石后，最长可能的最短跳跃距离是多少？输入第一行包含三个整数L, N,