题目链接:传送门
题目大意:
给出n根长度为1-1e5的电线,想要从中切割出k段等长的部分(不可拼接),问这个k段等长的电线最长可以是多长(保留两位小数向下取整)。
思路:
很裸的题意,二分答案即可。
但是如果使用double类型的二分会有浮点误差。
比如答案为2.50,二分的右区间r也为2.50时,则不管怎么二分,mid总是小于右区间的。也就是说mid最大只能取到2.50-eps/2 = 2.4999995,根据题意保留两位小数向下取整后的值就是2.49了。
因此对于这题的向下取整,在取整操作之前,可以加一个 += eps,就可以避免这种浮点误差了。
同样地如果一个题目要向上取整的话,可以加一个 -= eps,从而避免浮点误差。
#include <cstdio> #include <iostream> #include <algorithm> using namespace std; const int MAX_N = 1e4 + 5; const double eps = 1e-6; int n, k; double a[MAX_N]; bool check(double mid) { int sum = 0; for (int i = 1; i <= n; i++) { sum += (int)(a[i]/mid); } return sum >= k; } int main() { while (cin >> n >> k) { double sum = 0; for (int i = 1; i <= n; i++) { scanf("%lf", &a[i]); sum += a[i]; } double ans = 0; double l = 0, r = sum / k; while (r-l > eps) { double mid = l + (r - l) / 2.0; if (check(mid)) { ans = max(ans, mid); l = mid; } else { r = mid; } } ans += eps; ans = (int)(ans*100)/100.0; printf("%.2f ", ans); // r = (int)(r*100)/100.0; // printf("%.2f ", r); } return 0; } /* 4 11 8.02 7.43 4.57 5.39 4 14 5.99 8.00 8.00 6.00 2 5 5.99 0.99 */