题解

72 条题解

  • 0
    @ 2008-09-27 21:52:30

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 25ms

    ├ 测试数据 08:答案正确... 103ms

    ├ 测试数据 09:答案正确... 72ms

    ├ 测试数据 10:答案正确... 72ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:272ms

    我的AC率啊!!!!!!!!!!!!!!!!!!!!!哭!!!!!!!!!!!!!!!!!!!!!

    program p1450;

    var i,j,k,m,n:longint;

    a,b,c:array[0..200001]of longint;

    x,y:int64;

    t:boolean;

    v,wh:extended;

    function ok(v:extended):boolean;

    var now:extended;

    begin

    ok:=true;

    now:=0;

    for I:=1 to n do

    begin

    if (b[i]-now)*v=c[i] then

    now:=a[i]

    else now:=now+c[i]/v;

    end;

    end;

    procedure work(x,y:int64);

    var v:extended;

    wh:int64;

    begin

    if y-x>5 then

    begin

    wh:=(x+y) div 2;

    v:=wh/1000;

    t:=ok(v);

    if t then work(x,wh)

    else work(wh,y);

    end

    else

    begin

    write(x/1000:0:2);

    halt;

    end;

    end;

    begin

    readln(n);

    for i:=1 to n do

    readln(a[i],b[i],c[i]);

    work(0,100000000000);

    end.

  • 0
    @ 2008-09-27 10:44:43

    二分加贪心..

    不过...用double过不了 T_T..

    最后才发现竟然要用extended...

  • 0
    @ 2008-09-27 09:31:20

    二分很好,楼下很强大。

  • 0
    @ 2008-09-26 16:07:38

    二分果然是王道....

    可惜我一开始想成了动规...............汗死~~~~~~

  • 0
    @ 2008-09-25 22:31:44

    神七上天了

  • 0
    @ 2008-09-25 19:59:18

    谁能帮我看看哪里错了??????为什么只能过四个点?

    每次取一个区间的结束位置和上一个区间的开始位置的时间差,然后用他们之间的距离除这个时间,得出一个速度。

    可以想象,可以得到n个速度,在这n个速度里选取一个最大值max。这就是所要求的最大速度的最小值。

    下面说明一下:

    如果“最大速度的最小值”比这n个速度中的任何一个小,那是不可能的,因为如果比这个速度小,那必然有一段区间是不能按时达到的(这是很显然的)

    这就说明了‘最大速度的最小值’不会比max这个速度小。

    下面证明能取到:

    1.如果他在一段之内不用等待,那么用max肯定在这一段时间内能满足;

    2.如果需要等待,那么又重复了1这个过程。

    实际上就是分成很多段不用等待的区间集合。

    readln(n);

    with v0 do

    begin

    x:=0;y:=0;s:=0;

    end;

    for i:=1 to n do

    begin

    with v1 do

    begin

    readln(x,y,s)

    end;

    tmp:=v1.s/(v1.y-v0.x);

    if max

    • @ 2017-07-16 19:51:20

      实际上一定跑到的速度一定会是这个最小值吗?不会比这个大吗?我表示和你一样,感觉用了贪心

  • 0
    @ 2008-09-25 11:34:04

    程序简单,不到30行

    但是思想太棒了,赞一个

  • 0
    @ 2008-09-24 22:33:53

    本题的第800次提交

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 41ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 41ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:82ms

  • 0
    @ 2008-10-14 19:40:11

    先前我的一维递推题解是完全错的,只不过是凑得好.

    若有递推者可发程序给我,我能设计出过不了的点.

    所谓的数学方法是错的.

  • 0
    @ 2008-09-24 21:23:54

    l:=0;r:=10000000;

    while r-l>0.001 do

    begin

    m:=(l+r)/ 2;

    if try then r:=m

    else l:=m;

    end;

    刚开始是0.05,wa了。。90.。

    改成0.01.。wa了更多了。。40.。。

    其实是要0.001.。。AC

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 25ms

    ├ 测试数据 08:答案正确... 41ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 41ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:107ms

  • 0
    @ 2008-09-24 19:14:54

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 9ms

    ├ 测试数据 08:答案正确... 88ms

    ├ 测试数据 09:答案正确... 41ms

    ├ 测试数据 10:答案正确... 25ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:163ms

    haha

  • 0
    @ 2008-09-24 18:36:10

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 41ms

    ├ 测试数据 08:答案正确... 56ms

    ├ 测试数据 09:答案正确... 56ms

    ├ 测试数据 10:答案正确... 72ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:225ms

  • 0
    @ 2008-09-23 18:42:52

    非常非常强烈地要求: 管理员更换第九组数据!!!!

    我也是第九个点 卡住了; 把 real 改成 double 也没过, 后来 用 extended 过的

  • 0
    @ 2008-09-23 19:42:09

    我用动态规划做只得了40分~~~

    编译通过...

    ├ 测试数据 01:答案错误... ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 02:答案错误... ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 03:答案错误... ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 04:答案错误... ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 05:答案错误... ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 25ms

    ├ 测试数据 09:答案正确... 56ms

    ├ 测试数据 10:答案错误... ├ 标准行输出

     ├ 错误行输出

    ---|---|---|---|---|---|---|---|-

    Unaccepted 有效得分:40 有效耗时:81ms

    begin

    read(x[1],x[2],s);

    for i:=1 to 2 do

    for j:=1 to 2 do

    begin

    if x[j]>x0[i] then

    begin

    v:=s/(x[j]-x0[i]);

    if v-f>0.0001 then f:=v;

    end else f:=9999999999999.0;

    end;

    x0[1]:=x[1]; x0[2]:=x[2];

    end;

    请大牛指点下我的思路错在哪里!谢谢!!!

    我知道什么原因了!考虑不够充分!想当然了!不过也学了一种方法~

    但是我的方法居然过了4个点....

  • 0
    @ 2008-09-23 16:49:44

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 41ms

    ├ 测试数据 08:答案正确... 56ms

    ├ 测试数据 09:答案正确... 9ms

    ├ 测试数据 10:答案正确... 103ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:209ms

    二分答案,注意精度!

  • 0
    @ 2008-09-23 09:37:11

    非常感谢Orz教主_iek.chan对本菜的指导 思路非常巧妙

    具体解释一下 iek.chan的思路(我发现 他不舍得说...)

    怎样二分就不详细说了 注意区间右端点要足够大

    二分出一个速度 判断以这个速度是否所有段都可在规定时间段内完成(具体怎样判断 因为只有一小点技巧 请自行编写) 是则取二分区间中点左边一部分继续二分 否则取右边继续进行二分 逐步逼近最小值 到需要的精度停止即可

    为什么这样就是正解呢?

    证明:

    因为取得最大速度的这一段之外的每一段的速度都不大于这个最大速度 所以无论如何这个速度都是可以在规定时间段内完成每一段的 所以 全程都用这个最大速度与每段速度不一是没有区别的(当然只是对出解来说)

    证毕....(喂喂 这算啥子证明?)

    再次感谢iek.chan大牛....

  • 0
    @ 2008-09-22 20:05:46

    慢哪..

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 88ms

    ├ 测试数据 08:答案正确... 103ms

    ├ 测试数据 09:答案正确... 119ms

    ├ 测试数据 10:答案正确... 56ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:366ms

  • 0
    @ 2008-09-22 19:20:45

    非常非常强烈地要求:管理员更换第九组数据!!!!

    坑害了太多人啊.....

    也包括坑害了我的5次提交!!!!....

  • 0
    @ 2008-09-22 13:40:13

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 25ms

    ├ 测试数据 08:答案正确... 88ms

    ├ 测试数据 09:答案正确... 119ms

    ├ 测试数据 10:答案正确... 150ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:382ms

    RP问题......

  • 0
    @ 2008-09-22 13:37:57

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 9ms

    ├ 测试数据 08:答案正确... 88ms

    ├ 测试数据 09:答案正确... 88ms

    ├ 测试数据 10:答案正确... 150ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:335ms

    纪念下

信息

ID
1450
难度
7
分类
其他 | 二分查找 点击显示
标签
递交数
2952
已通过
508
通过率
17%
被复制
11
上传者