华为OD机试 :找终点

目录

题目大意

给定一个正整数数组,最大为100个成员,从第一个成员开始,走到数组最后一个成员最少的步骤数。第一步必须从第一元素开始,1<=步长<len/2, 第二步开始以所在成员的数字走相应的步数,如果目标不可达返回-1,只输出最少的步骤数。

样例输入

7 5 9 4 2 6 8 3 5 4 3 9

样例输出

2

说明

第一步:第一个可选步长选择2,第一个成员7走第2个成员,第二步,第2个成员为9,经过9个成员到最后

代码实现

#include <iostream>
#include <array>

constexpr int LENGTH = 100;

int FindFinish(std::array<int, LENGTH> arr, int n)
{
    int min = 100;
    
    for (int i = 1; i < n / 2; ++i) {
        int path = 0;
        
        for (int j = i; j < n; j += arr[j]) {
            ++path;
            
            if (j == n - 1) {
                min = min < path ? min : path;
                break;
            }
        }
    }
    
    if (min == 100) {
        return -1;
    }
    
    return min;
}

int main(void)
{
    std::array<int, LENGTH> arr {};
    int index = 0;
    
    while (std::cin.peek() != '\n') {
        std::cin >> arr[index++];
    }
    
    std::cout << FindFinish(arr, index) << std::endl;
    
    return 0;
}

个人主页:

www.codeapes.cn

上一篇:德科华为od机试编程题


下一篇:OD之绕过序列号验证(二)