今晚舉行的騰訊編程馬拉松，監(jiān)考過程看到第二題居然一直沒人做出來，忍不住手癢做了一下。題目如下
賽車手 返回比賽首頁
古哥是騰訊著名的賽車手。在一次特殊的內(nèi)部賽車比賽中，古哥為了體現(xiàn)出他對參賽MM的關(guān)照，約定在比賽過程中有車速限制，每一個這樣的限制都可以描述為一個三元組(s,t,d)，表示在比賽的t時間開始，持續(xù)d時間的過程中，古哥的車速不會超過s.古哥為了在這種情況下依舊證明他強大的實力，想讓聰明的你幫他求出在給定比賽時間T內(nèi)，賽車的加速度最大為a的情況下，古哥可能行駛的最遠距離。
PS：車速初始為0.
輸入:
第一行為一個數(shù)Cases，用來描述有多少組數(shù)據(jù)。
對于每組測試數(shù)據(jù)，首先為一個數(shù) n (0<=n<=50) 表示有 n個速度限制的三元組(s,t,d) 其中 0<=s<=100，0<=t<=T，0<=d<=1000
接下來為兩個正整數(shù)T a，用來描述比賽總時長和汽車的最大加速度。其中0<=T<=1000， 0<=a<=25
輸出:
對于每個測試數(shù)據(jù),輸出古哥可能行駛的最遠距離，精確到0.0001。
樣例輸入：
2
0
998 1
2
10 10 10
20 30 20
50 1
樣例輸出：
498002.0000
700.0000
我用js（非指定競賽語言），在規(guī)定時間內(nèi)做到這樣：
<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>
結(jié)果還是差了臨門一腳：
誰想出來的在一秒內(nèi)還可以加速半秒減速半秒這么損的招啊？