笔试真题笔记(持续更新)

系统管理员 2021-10-01 04:58 365阅读 0赞

# 笔试真题 #

*  **`腾讯2019秋招笔试真题`**

> **小Q爬塔**
> 
> 【题目描述】小Q正在攀爬一座宝塔，这座宝塔很特别，塔总共有n层，但是每两层之间的净高却不相同，所以造成了小Q爬过每层的时间也不同。如果某一层的高度为x，那么爬过这一层所需的时间也是x。小Q还会使用一种魔法，每用一次可以让他向上跳一层或两层，但是每次跳跃后小Q都将用完魔力，必须爬过至少一层才能再次跳跃（你可以认为小Q需要跳两次一层才休息，最后也可以跳到塔外即超过塔高，跳是不消耗时间的）。
> 
> 小Q想用最短的时间爬到塔顶，希望你能告诉他最短时间是多少。
> 
> **输入描述:**
> 
> 第一行一个数n（n<=10000），表示塔的层数。
> 
> 接下来的n行每行一个数h（ 1<= h <=100 ），表示从下往上每层的高度。
> 
> **输入样例:**
> 
> 5 3 5 1 8 4
> 
> **输出样例:**
> 
> 1

> #### 解题思路: ####
> 
> p\[ i \] 表示到达第i层的最短时间，并且到达第 i 层的方式是【爬】。
> 
> t\[ i \] 表示到达第i层的最短时间，并且到达第 i 层的方式是【跳】。
> 
> 到达第 i 层的方式采用爬还是跳：
> 
>     情况1.到达第 i 层的方式是爬：
>         那么到达第 i-1 层的方式可以是爬也可以是跳，从两者中选择最小。
>         p[i] = min( p[i-1] , t[i-1] ) + a[i]
> 
>     情况2.到达第 i 层的方式是跳：
>         那么可以从第 i-1 层起跳。也可以从第i-2层起跳。并且到达第 i-1 层和 i-2 层的方式只能是选择爬，所以在两者中选最小。
>         t[i] = min( p[i-1] , p[i-2] )
> 
> 最后在 p\[ n \] 和 t\[ n \] 中选择 最小者做结果

> **代码**：
> 
>     #include<stdio.h>
>     #define min(a,b) (((a)>(b)) ? (b):(a))
>     
>     int p[10005],t[10005];
>     
>     void main(){
>         int i,n,x;
>         scanf("%d",&n);
>     
>         for( i=1; i<=n; i++ ){
>             scanf("%d",&x);
>             p[i] = min(p[i-1],t[i-1])+x;
>             if (i==1)continue;
>             t[i] = min(p[i-1],p[i-2]);
>         }
>         printf("最少时间是%d\n",min(p[n],t[n]));
>     }
> 
> **输出结果**：
> 
>     5 3 5 1 8 4
>     a[1] = 3        p[1] = 3        t[1] = 0
>     a[2] = 5        p[2] = 5        t[2] = 0
>     a[3] = 1        p[3] = 1        t[3] = 3
>     a[4] = 8        p[4] = 9        t[4] = 1
>     a[5] = 4        p[5] = 5        t[5] = 1
>     最少时间是1
>     Press any key to continue

转载于:https://www.cnblogs.com/pipemm/articles/11108343.html