今日头条春招第一次笔试题(四)

第四题

题目描述

小T最近迷上了一款跳板小游戏
已知空中有N个高度互不相同的跳板,小T刚开始在高度为0的地方,每次跳跃可以选择与自己当前高度绝对值差小于等于H的跳板,跳跃过后到达以跳板为轴的镜像位置,问小T在最多跳K次的情况下最高能跳多高?(任意时刻高度不能为负).

输入描述

第一行三个整数N,K,H
一下N行,每行一个整数Ti,表示第i个跳板的离地高度.

输出描述:

一个整数,表示最高能跳到的高度.

解法分析

同样是决策树的问题,到达最大跳跃次数,或者没有可以跳的跳板,或者高度为负数则决策结束.采用递归可能不是最优的办法,但一定是可以解决的办法. 不保证正确性,并且赌一毛钱肯定不是最优的.只是一种平凡的解法.

代码

#include <iostream>
#include <vector>
using namespace std;

void find_max_height(int* height, int n, int k, int h, int height_now, int times_now);
bool binary_find(const int* height, int begin, int end, int target);
int max_height = 0;

int main() {
    std::cout << "Hello, World!" << std::endl;
    int n, k, h;
    cin >> n >> k >> h;
    int height[n];
    for(int i =0; i < n; i++)
    {
        cin >> height[i];
    }
    find_max_height(height, n, k, h, 0, 0);
    cout << max_height;
    return 0;
}

void find_max_height(int* height, int n, int k, int h, int height_now, int times_now)
{
    if(height_now > max_height)
        max_height = height_now;
    if(times_now < k && height_now >=0)
    {
        for(int i = height_now - h; i <= height_now + h; i++)
        {
            if(binary_find(height, 0, n-1, i))
            {

                find_max_height(height, n, k, h, i * 2 - height_now, times_now + 1);
            }
        }
    }
}
bool binary_find(const int* height, int begin, int end, int target)
{
    while(begin <= end)
    {
        int mid = (begin + end) / 2;
        if(height[mid] < target)
            begin = mid + 1;
        else if(height[mid] > target)
            end = mid - 1;
        else
            return true;
    }
    return false;
}