狮驼岭探路（C++、C语言）

题目描述
唐僧师徒四人行至狮驼岭，由于太白金星的警告，唐僧决定让孙悟空先探一探妖怪的动向。

已知孙悟空探路一共会经过个n地点，每个地点有一个高度h[i]，中间会有若干个山头。

一个“山头”的定义是：存在一个地点，它的高度严格大于（即不含等号）前一个和后一个地点。首尾两端只要高于旁边一侧地点就属于"山头"。

为了找到最佳观测地点，于是他决定在探路路线上找最中间位置的一个“山头”。请你帮助他找到这个山头的位置。

若山头有偶数个，则孙悟空会选择中间两个山头中靠近自己出发点的那一个；

如果没有合适的山头，请你输出-1，这样孙悟空只能直接返回。

输入格式
第一行输入一个数n，表示孙悟空探路经过的地点数；

第二行输入n个整数h[i]，表示从出发点开始经过每个地点的高度。

输出格式
输出一个数，表示孙悟空需要选择第几个地点进行观测。

若没有出现山头，则输出"-1"（不含双引号）。

img

int h[2001]保存所有的地点高度；
int st[2001]保存所有山头的编号；
int cnt = 0；保存山头的个数
读取地点高度后，按照规则找出所有山头保存到st中，根据cnt的数量和奇偶性输出即可。
运行结果如下：

img

C代码：

#include <stdio.h>
int main()
{
    int h[2001] = { 0 }, n;
    int st[2001] = { 0 }; //存储所有山头的编号
    int cnt = 0; //山头的个数
    int i;
    int index = 0;

    scanf("%d", &n); //输入n
    for (i = 0; i < n; i++)
        scanf("%d",&h[i]);
    //判断第一个地点
    if (h[0] > h[1])
    {
        st[cnt] = 1; //山头编号从1开始
        cnt++;
    }
    //判断中间的地点
    for (i = 1; i < n - 1; i++)
    {
        if (h[i] > h[i - 1] && h[i] > h[i + 1])
        {
            st[cnt] = i + 1;
            cnt++;
        }
    }
    //判断最后一个地点
    if (n >= 2 && h[n - 1] > h[n - 2])
    {
        st[cnt] = n;
        cnt++;
    }

    if (cnt == 0)
        printf("-1"); //没有山头
    else
    {
        if (cnt % 2 == 0) //偶数个山头
            printf("%d", st[cnt / 2 - 1]);
        else
            printf("%d",st[cnt / 2]);
    }
    return 0;
}

C++代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;
int main()
{
    int h[2001] = { 0 }, n;
    int st[2001] = { 0 }; //存储所有山头的编号
    int cnt = 0; //山头的个数
    int i, j;
    int index = 0;

    cin >> n; //输入n
    for (i = 0; i < n; i++)
        cin >> h[i];
    //判断第一个地点
    if (h[0] > h[1])
    {
        st[cnt] = 1; //山头编号从1开始
        cnt++;
    }
    //判断中间的地点
    for (i = 1; i < n - 1; i++)
    {
        if (h[i] > h[i - 1] && h[i] > h[i + 1])
        {
            st[cnt] = i + 1;
            cnt++;
        }
    }
    //判断最后一个地点
    if (n >= 2 && h[n - 1] > h[n - 2])
    {
        st[cnt] = n;
        cnt++;
    }

    if (cnt == 0)
        cout <<"-1"; //没有山头
    else
    {
        if (cnt % 2 == 0) //偶数个山头
            cout << st[cnt / 2 - 1];
        else
            cout << st[cnt / 2];
    }
    return 0;
}


#include <stdio.h>
#define MAXN 2000
int main()
{
    int n, h[MAXN], cnt = 0, mid = 0, ans = -1;
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        scanf("%d", &h[i]);
    for(int i = 1; i < n-1; i++)
    {
        if(h[i] > h[i-1] && h[i] > h[i+1]) 
        {
            cnt++;
            if(cnt == 1)
                mid = i;
        }
        if(cnt == 2) 
        {
            ans = mid + (i-mid+1)/2; 
            break;
        }
    }
    printf("%d", ans);
    if(ans == -1)
        printf("\n");
    return 0;
}

这个典型的动态规划就可以实现的啦。

您好，我是有问必答小助手，您的问题已经有小伙伴帮您解答，感谢您对有问必答的支持与关注！
PS：问答VIP年卡 【限时加赠：IT技术图书免费领】，了解详情>>> https://vip.csdn.net/askvip?utm_source=1146287632