题目描述
给定 $n$ 条长度分别为 $a_i$ 的绳子，求切出 $k$ 条完整绳子的最大长度。
$1\le n\le 10^4$，$1\le k\le 10^4$，$a_i$ 有两位小数。
算法分析
二分答案，在长度为 $d$ 时能切出 $k$ 条完整的绳子显然在长度小于 $d$ 时也能做到，答案具有单调性。
重点是实现时考虑浮点运算精度问题，刚开始注意到 printf 在保留位数是会自动四舍五入，为了得到舍掉两位小数后的全部低位，在结果最后额外减去了 $0.005$，然而依然有浮点误差。
索性用整数实现，很快就解决了hhh，详细见代码。
代码实现
C++ 实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include <cstdio>
#include <algorithm>
#define N 10005
int n,k,a[N];
inline bool check(int d) {
int cnt=0;
for(int i=0;i<n;++i) cnt+=a[i]/d;
return cnt>=k;
}
int main() {
scanf("%d%d",&n,&k);
int l=0,r=0;
for(int i=0;i<n;++i) {double d;scanf("%lf",&d);r=std::max(r,a[i]=d*100);}
while(l<r) {
int mid=(l+r+1)>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
printf("%d.%02d\n",l/100,l%100);
return 0;
}
|
Java 实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| import java.util.Scanner;
public class Main {
static int n, k;
static int[] a;
private static boolean check(int d) {
int cnt = 0;
for(int i = 0; i < n; ++i) cnt += a[i] / d;
return cnt >= k;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
n = in.nextInt();
k = in.nextInt();
a = new int[n];
int l = 0, r = 0;
for(int i = 0; i < n; ++i) {
double d = in.nextDouble();
a[i] = (int)(100.0 * d);
r = Math.max(r, a[i]);
}
while(l < r) {
int mid = (l + r + 1) >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
System.out.printf("%d.%02d\n",l / 100, l % 100);
}
}
|