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

. . 01:查找最接近的元素

描述 在一个非降序列中，查找与给定值最接近的元素。

输入 第一行包含一个整数n，为非降序列长度。1 <= n <= 100000。 第二行包含n个整数，为非降序列各元素。所有元素的大小均在0-1,000,000,000之间。

第三行包含一个整数m，为要询问的给定值个数。1 <= m <= 10000。 接下来m行，每行一个整数，为要询问最接近元素的给定值。所有给定值的大小均在0-1,000,000,000之间。

输出 m行，每行一个整数，为最接近相应给定值的元素值，保持输入顺序。若有多个值满足条件，输出最小的一个。

样例输入 3 2 5 8 2 10 5

样例输出 8 5 .

. 02:二分法求函数的零点 • 查看 • 提交 • 统计 • 提问 总时间限制: 1000ms

内存限制: 65536kB

描述 有函数： f(x) = x5 - 15 * x4+ 85 * x3- 225 * x2+ 274 * x - 121 已知 f(1.5) > 0 , f(2.4) < 0 且方程 f(x) = 0 在区间 [1.5,2.4] 有且只有一个根，请用二分法求出该根。

输入 无。

输出 该方程在区间[1.5,2.4]中的根。要求四舍五入到小数点后6位。

样例输入 无

样例输出 不提供 .

. 03:切分矩形组 • 查看 • 提交 • 统计 • 提问 总时间限制: 1000ms

内存限制: 65536kB

描述 给定若干个平行于坐标轴的互不重叠的矩形，矩形的顶点都是整点。要求画一根平行于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。如果有多条直线满足要求，输出最小的k。

样例输入 2 1 1 100 100 1000 1 100 100

样例输出 101 . . 04:网线主管 描述 仙境的居民们决定举办一场程序设计区域赛。裁判委员会完全由自愿组成，他们承诺要组织一次史上最公正的比赛。他们决定将选手的电脑用星形拓扑结构连接在一起，即将它们全部连到一个单一的中心服务器。为了组织这个完全公正的比赛，裁判委员会主席提出要将所有选手的电脑等距离地围绕在服务器周围放置。 为购买网线，裁判委员会联系了当地的一个网络解决方案提供商，要求能够提供一定数量的等长网线。裁判委员会希望网线越长越好，这样选手们之间的距离可以尽可能远一些。 该公司的网线主管承接了这个任务。他知道库存中每条网线的长度（精确到厘米），并且只要告诉他所需的网线长度（精确到厘米），他都能够完成对网线的切割工作。但是，这次，所需的网线长度并不知道，这让网线主管不知所措。 你需要编写一个程序，帮助网线主管确定一个最长的网线长度，并且按此长度对库存中的网线进行切割，能够得到指定数量的网线。 输入 第一行包含两个整数N和K，以单个空格隔开。N（1 <= N <= 10000）是库存中的网线数，K（1 <= K <= 10000）是需要的网线数量。 接下来N行，每行一个数，为库存中每条网线的长度（单位：米）。所有网线的长度至少1m，至多100km。输入中的所有长度都精确到厘米，即保留到小数点后两位。 输出 网线主管能够从库存的网线中切出指定数量的网线的最长长度（单位：米）。必须精确到厘米，即保留到小数点后两位。 若无法得到长度至少为1cm的指定数量的网线，则必须输出“0.00”（不包含引号）。 样例输入

4 11 8.02 7.43 4.57 5.39

样例输出 2.00 来源 Northeastern Europe 2001 .

. 05:派

描述 我的生日要到了！根据习俗，我需要将一些派分给大家。我有N个不同口味、不同大小的派。有F个朋友会来参加我的派对，每个人会拿到一块派（必须一个派的一块，不能由几个派的小块拼成；可以是一整个派）。

我的朋友们都特别小气，如果有人拿到更大的一块，就会开始抱怨。因此所有人拿到的派是同样大小的（但不需要是同样形状的），虽然这样有些派会被浪费，但总比搞砸整个派对好。当然，我也要给自己留一块，而这一块也要和其他人的同样大小。

请问我们每个人拿到的派最大是多少？每个派都是一个高为1，半径不等的圆柱体。

输入 第一行包含两个正整数N和F，1 ≤ N, F ≤ 10 000，表示派的数量和朋友的数量。 第二行包含N个1到10000之间的整数，表示每个派的半径。

输出 输出每个人能得到的最大的派的体积，精确到小数点后三位。

样例输入 3 3 4 3 3

样例输出 25.133 .

. 06:月度开销

描述 农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来 N (1 ≤ N ≤ 100,000) 天里每天需要的开销。 约翰打算为连续的M (1 ≤ M ≤ N) 个财政周期创建预算案，他把一个财政周期命名为fajo月。每个fajo月包含一天或连续的多天，每天被恰好包含在一个fajo月里。 约翰的目标是合理安排每个fajo月包含的天数，使得开销最多的fajo月的开销尽可能少。

输入 第一行包含两个整数N,M，用单个空格隔开。 接下来N行，每行包含一个1到10000之间的整数，按顺序给出接下来N天里每天的开销。

输出 一个整数，即最大月度开销的最小值。

样例输入 7 5 100 400 300 100 500 101 400

样例输出 500

提示 若约翰将前两天作为一个月，第三、四两天作为一个月，最后三天作为一个月，则最大月度开销为500。其他任何分配方案都会比这个值更大。 . . 07:和为给定数 • 查看 • 提交 • 统计 • 提问 总时间限制: 1000ms

内存限制: 65536kB

描述 给出若干个整数，询问其中是否有一对数的和等于给定的数。

输入 共三行： 第一行是整数n(0 < n <= 100,000)，表示有n个整数。 第二行是n个整数。整数的范围是在0到10^8之间。 第三行是一个整数m（0 <= m <= 2^30)，表示需要得到的和。

输出 若存在和为m的数对，输出两个整数，小的在前，大的在后，中间用单个空格隔开。若有多个数对满足条件，选择数对中较小的数更小的。若找不到符合要求的数对，输出一行No。

样例输入 4 2 5 1 4 6

样例输出 1 5 . . 08:不重复地输出数 • 查看 • 提交 • 统计 • 提问 总时间限制: 1000ms

内存限制: 65536kB

描述 输入n个数，从小到大将它们输出，重复的数只输出一次。保证不同的数不超过500个。

输入 第一行是一个整数n。1 <= n <= 100000。 之后n行，每行一个整数。整数大小在int范围内。

输出 一行，从小到大不重复地输出这些数，相邻两个数之间用单个空格隔开。

样例输入 5 2 4 4 5 1

样例输出 1 2 4 5 .

. 09:膨胀的木棍 描述 当长度为L的一根细木棍的温度升高n度，它会膨胀到新的长度L'=(1+n*C)*L，其中C是热膨胀系数。

当一根细木棍被嵌在两堵墙之间被加热，它将膨胀形成弓形的弧，而这个弓形的弦恰好是未加热前木棍的原始位置。

你的任务是计算木棍中心的偏移距离。

输入 三个非负实数：木棍初始长度（单位：毫米），温度变化（单位：度），以及材料的热膨胀系数。 保证木棍不会膨胀到超过原始长度的1.5倍。

输出 木棍中心的偏移距离（单位：毫米），保留到小数点后第三位。

样例输入 1000 100 0.0001

样例输出 61.329