POJ1064 Cable master

题目大意：有N根长度不一的电缆，要以它们为基础通过截断得到K根长度相等的电缆，求能得到的等长电缆的最大长度。

输入：第一行分别是N和K。N和K都在1到10000之间。接下来N行每行一个数组表示一根现有电缆的长度，都保留到小数点后两位。

输出：可能得到的等长电缆的最大长度，输出为两位小数。如果不能得到K根长度大于0.01的等长电缆电缆应输出0.00.

Sample Input

Sample Output

2.00

可以用二分查找的方法来找答案。首先确定查找的区间上下界。下界为0.01, 上界为所有电缆中最长的那根。这里容易出错的地方是，上界不应该是最短电缆长度，因为题目没有要求要用上所有的电缆，不要被之前做过的一道坎木棍的题目扰乱了思路。确定了上下界之后用二分法查找最大值。若长度x可达，则继续查找大于x的区间看是否能找到更大的值，如x不可达，则查找小于x的区间。还有一个问题是这里我们要进行二分查找的对象是浮点数，于是要考虑精度的问题，一个是查找精度的问题，还有一个是在确认某长度值是否可行时会有除法运算，也会涉及到精度问题，而且在这里的除法结果理论上应该要对结果采用“全舍”而不是“四舍五入”。这些问题虽不算太麻烦，但是因为题目里输入和输出的精度都在小数点后两位，我们如果把数值全部乘以100，转化为在整数上的二分，那么既可以避免精度问题，又提升了程序速度。以下是AC代码：

 1 ////////////////////////////////////////////////////////////////
 2 //        POJ1064 Cable master
 3 //        Memory: 184K        Time: 63MS
 4 //        Language: C++        Result : Accepted
 5 ////////////////////////////////////////////////////////////////
 6 
 7 #include <cstdio>
 8 
 9 using namespace std;
10 
11 int main(void) {
12     int n, k;
13     int s[10000], len = 0, max = 0;
14     scanf("%d%d", &n, &k);
15     for (int i = 0; i < n; ++i) {
16         double buf;
17         scanf("%lf", &buf);
18         s[i] = buf * 100;
19         max = s[i] < max ? max : s[i];
20     }
21     int low = 1, high = max;
22     int mid, sum, ans = 0;
23     while (low <= high) {
24         mid = (low + high) / 2;
25         sum = 0;
26         for (int i = 0; i < n; ++i) {
27             sum += s[i] / mid;
28         }
29         if (sum >= k) {
30             ans = mid > ans ? mid : ans;
31             low = mid + 1;
32         }
33         else {
34             high = mid - 1;
35         }
36     }
37     printf("%d.%02d 
", ans / 100, ans % 100);
38     return 0;
39 }

View Code

最近装的VS2013居然直接不让用scanf函数了，无语= =! 但是据说不用scanf的话会超时？所以如果用vs2013的话需要在程序里加入这行代码：

1 #pragma warning(disable:4996)