emu in blogjava

  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  171 随笔 :: 103 文章 :: 1052 评论 :: 2 Trackbacks
今晚举行的腾讯编程马拉松,监考过程看到第二题居然一直没人做出来,忍不住手痒做了一下。题目如下

赛车手 返回比赛首页
古哥是腾讯著名的赛车手。在一次特殊的内部赛车比赛中,古哥为了体现出他对参赛MM的关照,约定在比赛过程中有车速限制,每一个这样的限制都可以描述为一个三元组(s,t,d),表示在比赛的t时间开始,持续d时间的过程中,古哥的车速不会超过s.古哥为了在这种情况下依旧证明他强大的实力,想让聪明的你帮他求出在给定比赛时间T内,赛车的加速度最大为a的情况下,古哥可能行驶的最远距离。
PS:车速初始为0.
输入:
第一行为一个数Cases,用来描述有多少组数据。
对于每组测试数据,首先为一个数 n (0<=n<=50) 表示有 n个速度限制的三元组(s,t,d) 其中 0<=s<=100,0<=t<=T,0<=d<=1000
接下来为两个正整数T a,用来描述比赛总时长和汽车的最大加速度。其中0<=T<=1000, 0<=a<=25
输出:
对于每个测试数据,输出古哥可能行驶的最远距离,精确到0.0001。
样例输入:
2
0
998 1
2
10 10 10
20 30 20
50 1
样例输出:
498002.0000
700.0000

我用js(非指定竞赛语言),在规定时间内做到这样:
<html>
<head></head>
<body>
<textarea>2
0
998 1
2
10 10 10
20 30 20
50 1
5
2 1 2
6 4 3
4 7 1
5 10 1
1 12 1
12 2</textarea>
<script>
var data=document.getElementsByTagName("textarea")[0].value.split("\n");
var idx=0;
for(var i=1;i<data[0]+1;i++){
var limits=[]
    n
=data[++idx];
    
for(var j=0;j<n;j++){
        limits.push(data[
++idx].split(" "))
    }
    tmp
=data[++idx].split(" ");
    T
=tmp[0]-0;
    a
=tmp[1]-0;
    
var speedAtRealTime=new Array(T+1);
    speedAtRealTime[
0]=0;
    
for(var j=1;j<=T;j++){
        speedAtRealTime[j]
=speedAtRealTime[j-1]+a;
    }
    
for(var j=0;j<limits.length;j++){
        
for(var k=limits[j][1];k<=limits[j][1]-(-limits[j][2]);k++){
            
if(speedAtRealTime[k]>limits[j][0]-0){
                speedAtRealTime[k]
=limits[j][0]-0;
            }
        }
    }
    
var adjustSpeed=true;
    
while(adjustSpeed){
        adjustSpeed
=false;
        
for(var j=1;j<=T;j++){
            
if(speedAtRealTime[j]-speedAtRealTime[j-1]>a){//加速不了那么快
                speedAtRealTime[j]=speedAtRealTime[j-1]+a;
                adjustSpeed
=true;
            }
        }
        
for(var j=T;j>0;j--){
            
if(speedAtRealTime[j-1]-speedAtRealTime[j]>a){//要提前减速
            
                speedAtRealTime[j
-1]=speedAtRealTime[j]+a;
                adjustSpeed
=true;
            }
        }
    }
     alert(speedAtRealTime.join(
","));
     
var length=0
    
for(var j=1;j<speedAtRealTime.length;j++){
        length
+=speedAtRealTime[j-1]+speedAtRealTime[j]
    }
    length
=length/2;
    alert(length)
}
</script>
</body>
</html>

结果还是差了临门一脚:
1
0 1 0
1 1
正确输出:
0.2500
谁想出来的在一秒内还可以加速半秒减速半秒这么损的招啊?



posted on 2012-09-09 22:40 emu 阅读(1740) 评论(0)  编辑  收藏 所属分类: google编程大赛模拟题及入围赛真题

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


网站导航: