P1577 切绳子 (二分答案Java)

P1577 切绳子

题目描述

有 N 条绳子，它们的长度分别为 Li。如果从它们中切割出 K 条长度相同的绳子，这 K 条绳子每条最长能有多长？答案保留到小数点后 2 位(直接舍掉 2 位后的小数)。

输入格式

第一行两个整数 N 和 K，接下来 N 行，描述了每条绳子的长度 Li。

输出格式

切割后每条绳子的最大长度。答案与标准答案误差不超过 0.01 或者相对误差不超过 1% 即可通过。

输入输出样例

输入 #1
4 11
8.02
7.43
4.57
5.39
输出 #1
2.00

解题思路：

二分答案模板题

代码如下：

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);long n, k, ans = 0, l, r, mid = 0;long[] a = new long[10010];double[] b = new double[10010];double t;n = sc.nextLong();k = sc.nextLong();for (int i = 1; i <= n; i++) {b[i] = sc.nextDouble();a[i] = (long) (b[i] * 100);ans += a[i];}l = 0;r = ans / k + 1;while (l < r) {mid = (l + r + 1) / 2;ans = 0;for (int i = 1; i <= n; i++)ans += a[i] / mid;if (ans < k)r = mid - 1;elsel = mid;}t = r * 1.00 / 100;System.out.printf("%.2f", t);}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！