首页 > 代码库 > poj 1064

poj 1064

2024-09-14 09:56:01   216人阅读

http://poj.org/problem?id=1064

题意：就是有N条线段，要分成m段，求每段最大是多少

这个题挺有意思的。二分答案（答案的区间在0.01和max（len（n））之间)。

还有一个挺有意思的，就是我发现有个案例我过不了

4 2540        

8.02        

7.43 

4.57     

5.39 

这个我过不了，然后我debug的时候发现，我存的数据和这个不一样，我用Int存的，是每个扩大100倍，但是我的第一个数据变成了801

我在debug看的时候我发现了一个问题，输入8.02的值，在debug那个窗口显示的确实8.019999999,我感到很奇怪，然后查了一下，也明白了

因为数据在计算机中的存储都是以二进制来存的，但是0.2在计算机中表示不出来，那么计算机就用一个最接近它的值来表示这个数字

所以在进行扩大的时候，可以采取四舍五入的方式，这样就可以保证你在扩大的时候不会出现我这种问题，当然这个题的数据问题，不进行四舍五入也是可以过的

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 
 5 int n,m;
 6 int num[10005];
 7 double x;
 8 
 9 int cnt(int x)
10 {
11     int tmp = 0;
12     for(int i = 1;i<=n;i++)
13         tmp+=num[i]/x;
14     return tmp;
15 }
16 
17 
18 int main()
19 {
20     while(~scanf("%d%d",&n,&m))
21     {
22         int left = 1,Max = 0,ans = 0;
23         for(int i = 1;i<=n;i++)
24         {
25             scanf("%lf",&x);
26             num[i] = x*100;   //这里也可以改成（x+0.05）*100,这样更加的准确
27             if(num[i]>Max)
28                 Max = num[i];
29         }
30         while(left<=Max)
31         {
32             int mid = (left+Max)/2;
33             if(cnt(mid)>=m)
34             {
35                 left = mid+1;
36                 ans = mid;
37             }else
38             {
39                 Max = mid-1;
40             }
41         }
42         printf("%.2lf\n",ans*0.01);
43     }
44     return 0;
45 }

 

poj 1064


联系
我们