Snowdream

I'm awake but my world is half asleep
posts - 403, comments - 310, trackbacks - 0, articles - 7
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

URAL 1011

Posted on 2008-04-23 22:44 ZelluX 阅读(642) 评论(10)  编辑  收藏 所属分类: Algorithm

Problem

Every bus in the Ekaterinburg city has a special man (or woman) called conductor. When you ride the bus, you have to give money to the conductor. We know that there are more then P% conductors and less then Q% conductors. Your task is to determine a minimal possible number of Ekaterinburg citizens.


我只能说太挫了。。。精度问题搞了半天,看来浮点还是要尽量化成整型再算啊。


还有个问题就是q*i是开区间还是闭区间,总之Wrong Answer了无数次后总算过了。。。

评论

# re: URAL 1011  回复  更多评论   

2008-04-24 19:22 by luohandsome
double也不行么

# re: URAL 1011  回复  更多评论   

2008-04-24 20:53 by ZelluX
一开始用的是double,别人可以过,不过我搞不定,还是用整型了

# re: URAL 1011[未登录]  回复  更多评论   

2008-05-02 20:24 by dave
请教一下:
既然dp, dq只有两位小数,那么
int p = floor(dp * 100 + 0.5);

int p = dp * 100;
有区别吗?

# re: URAL 1011  回复  更多评论   

2008-05-03 09:03 by ZelluX
@dave
当然有,实际保存的时候是浮点啊,如果是dp = 49.9999999这种情况呢?

# re: URAL 1011[未登录]  回复  更多评论   

2008-05-03 13:18 by dave
谢谢。
那为什么要四舍五入呢?即int p = floor(dp * 100 + 0.5);中的"+0.5"?

# re: URAL 1011  回复  更多评论   

2008-05-03 17:33 by ZelluX
@dave
49.99999999这种情况不四舍五入不是就错了吗。。。

# re: URAL 1011[未登录]  回复  更多评论   

2008-05-04 10:36 by dave
我把“Numbers are given with 2 digits precision”理解为输入时即保证dp只有两位小数的,因此我开始认为int p = dp * 100;就可以了(因为dp * 100是正整数)。然而,实际的情况是:输入为double(小数点后6或7位),但程序只保存两位,因此需要四舍五入?但舍入误差会不会造成在某些输入数据下求得的i不是最小的满足条件的值(只不过原题测试数据较弱)?
如果这次理解仍然有误,请你稍微详细解释下。比如“49.99999999这种情况不四舍五入不是就错了吗”?

这一题看似简单,但的确烦人。打扰你了。谢谢。

# re: URAL 1011  回复  更多评论   

2008-05-04 11:44 by ZelluX
@dave
“只有两位小数”只是说输入的时候是这样,但实际读进来的时候是用double保存的,前者是定点,后者是浮点,转换的时候容易出现误差。
比如输入了48.00,有可能在操作过程中就变成47.9999999(关于这个问题可以看看Computer System: A Programmer's Perspective的第二张浮点部分)
对于这种情况就需要进行四舍五入了。
考虑到浮点误差的问题(另外浮点计算速度也比定点慢很多),所以我建议能用定点就尽量先转到定点。
int p = floor(dp * 100 + 0.5) 这样四舍五入就避免了浮点导致的误差。
之后再用定点(整型)计算就不会有误差了。

# re: URAL 1011[未登录]  回复  更多评论   

2008-05-04 15:05 by dave
非常感谢你的耐心,我明白了。
你的blog很棒,+U~

# re: URAL 1011  回复  更多评论   

2008-06-15 07:49 by 烁烁
有人会PAS版的吗?

只有注册用户登录后才能发表评论。


网站导航: