問題描述

"Help Jimmy" 是在下圖所示的場景上完成的游戲：

場景中包括多個長度和高度各不相同的平臺。地面是最低的平臺，高度為零，長度無限。

Jimmy 老鼠在時刻0 從高于所有平臺的某處開始下落，它的下落速度始終為1 米/秒。

當Jimmy 落到某個平臺上時，游戲者選擇讓它向左還是向右跑，它跑動的速度也是1 米/秒。

當Jimmy 跑到平臺的邊緣時，開始繼續(xù)下落。Jimmy 每次下落的高度不能超過MAX 米，不

然就會摔死，游戲也會結束。

設計一個程序，計算Jimmy 到地面時可能的最早時間。

輸入數(shù)據(jù)

第一行是測試數(shù)據(jù)的組數(shù) t（0 <= t <= 20）。每組測試數(shù)據(jù)的第一行是四個整數(shù)N，X，

Y，MAX，用空格分隔。N 是平臺的數(shù)目（不包括地面），X 和Y 是Jimmy 開始下落的位置

的橫豎坐標，MAX 是一次下落的最大高度。接下來的N 行每行描述一個平臺，包括三個整

數(shù)，X1[i]，X2[i]和H[i]。H[i]表示平臺的高度，X1[i]和X2[i]表示平臺左右端點的橫坐標。1

<= N <= 1000，-20000 <= X, X1[i], X2[i] <= 20000，0 < H[i] < Y <= 20000（i = 1..N）。所有坐

標的單位都是米。

Jimmy 的大小和平臺的厚度均忽略不計。如果Jimmy 恰好落在某個平臺的邊緣，被視

為落在平臺上。所有的平臺均不重疊或相連。測試數(shù)據(jù)保Jimmy 一定能安全到達地面。

輸出要求

對輸入的每組測試數(shù)據(jù)，輸出一個整數(shù)，Jimmy 到地面時可能的最早時間。

輸入樣例

1

3 8 17 20

0 10 8

0 10 13

4 14 3

輸出樣例

23

思路：

用一棵樹形保存每一個平臺，然后遞歸求解

#include <stdio.h> #include <stdlib.h> struct Line {int x1;int x2;int h;Line * Parent;Line * Left;Line * Right; };Line *line; int cmp(const void * a,const void * b) {Line *m,*n;m=(Line *)a;n=(Line *)b;if(m->h>n->h)return -1;else if(m->h==n->h){if(m->x1>n->x1)return -1;else return 1;}else {return 1;} } void tree(Line * lp,int i,int n,int max) {if(i+1<n-1){if(lp[i].x2>=lp[i+1].x2){lp[i].Left=&lp[i+1];tree(lp,i+1,n,max);if(i+2<n-1){for(int k=i+2;k<n;k++){if(lp[i].h-lp[k].h<=max){if(k==n-1){lp[i].Right=&lp[k];tree(lp,k,n,max);break;}else if(lp[i].x1<=lp[k].x1){lp[i].Right=&lp[k];tree(lp,k,n,max);break;}else {}}else{lp[i].Right=NULL;break;}}//for}else{lp[i].Right=&lp[n];}}else{lp[i].Right=&lp[i+1];tree(lp,i+1,n,max);for(int k=i+2;k<n;k++){if(lp[i].h-lp[k].h<=max){if(k==n-1){lp[i].Left=&lp[k];tree(lp,k,n,max);break;}else if(lp[i].x2>=lp[k].x2){lp[i].Left=&lp[k];tree(lp,k,n,max);break;}else{}}else{lp[i].Left=NULL;break;}}//for}}else{lp[i].Left=&lp[n];lp[i].Right=&lp[n];} }int min(int a,int b) {if(a<b)return a;else return b; }int cal(Line * lp,int x) {if(lp->Left==lp->Right){return min(lp->x2-x,x-lp->x1);}if(lp==NULL)return 10000000;return min(x-lp->x1+cal(lp->Left,lp->x1),lp->x2-x+cal(lp->Right,lp->x2)); }int main() {int t;scanf("%d",&t);for(int i=0;i<t;i++){int n,x,y,max;int res=0;scanf("%d%d%d%d",&n,&x,&y,&max);line=new Line[n+1];for(int i=0;i<n;i++){scanf("%d%d%d",&line[i].x1,&line[i].x2,&line[i].h);}//read itemsline[n].h=0;line[n].x1=0;line[n].x2=200000000;qsort(line,n+1,sizeof(Line),cmp);//sort items by highttree(line,0,n+1,max);res=y+cal(line,x);/*for(int i=0;i<n;i++){printf("line %d\nx1=%d x2=%d h=%d \n",i,line[i].x1,line[i].x2,line[i].h);}*/printf("%d\n",res);delete []line;}}

　　

轉載于:https://www.cnblogs.com/c840136/articles/2179365.html

總結

以上是生活随笔為你收集整理的Help Jimmy（递归）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。