编译通过...

├ 测试数据 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.

二分加贪心..

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

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

二分很好，楼下很强大。

二分果然是王道....

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

神七上天了

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

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

可以想象，可以得到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

程序简单,不到30行

但是思想太棒了,赞一个

本题的第800次提交

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

所谓的数学方法是错的.

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

haha

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

我用动态规划做只得了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个点....

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

二分答案,注意精度!

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

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

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

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

为什么这样就是正解呢?

证明：

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

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

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

慢哪..

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

RP问题......

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

纪念下