思路

这是一个典型的模拟题。我们需要按照题目描述的规则，一年一年地模拟山峰和山谷消失的过程，直到某一年不再有任何山消失为止。

核心模拟流程：

1. 数据结构：由于山会不断被移除，我们需要一个能够高效执行删除操作的数据结构。数组（如C++的 std::vector 或Java的 ArrayList）在删除中间元素时效率较低（时间复杂度为 $O(N)$），因为需要移动后续所有元素。相比之下，双向链表（如C++的 std::list 或Java的 LinkedList）是更理想的选择，因为它可以在 $O(1)$ 的时间内删除一个已知位置的元素。

2. 模拟循环：我们用一个变量 year 从 $1$ 开始计数，进入一个主循环。这个循环的终止条件是“某一年没有任何山消失”。

3. 识别山峰/山谷：在每一年中，我们首先需要判断是“山谷年”（year 为奇数）还是“山峰年”（year 为偶数）。然后，我们遍历当前所有的山（注意要排除首尾两座），根据定义（山谷：$h_{i} < h_{i-1}$ 且 $h_{i} < h_{i+1}$；山峰：$h_{i} > h_{i-1}$ 且 $h_{i} > h_{i+1}$）来找出所有符合条件的山。

4. 同步删除：这是一个关键点。题目要求“所有”山谷或山峰“同时”消失。这意味着我们不能在遍历过程中发现一个就立即删除一个，因为删除一个山会改变其邻居的相邻关系，从而影响后续的判断。

   • 正确做法是：先遍历一遍，将所有待删除的山的位置（例如，在链表中的迭代器或在数组中的索引）记录在一个临时列表中。
   • 遍历结束后，再根据这个临时列表，将这些山从主数据结构中统一删除。

5. 终止条件：在一次完整的识别过程后，如果发现临时列表是空的，说明在当前这一年，没有符合消失条件的山。这正是我们寻找的时刻。此时，循环结束，当前的 year 值就是答案。

6. 循环继续：如果临时列表不为空，说明今年有山消失了。我们就执行删除操作，然后将 year 加 $1$，进入下一年的模拟。

算法总结：

• 初始化 year = 1。

• 使用一个双向链表存储山的高度。

• while (true) 循环：

  • 创建一个空的临时列表 to_remove 来存储待删除的山的位置。
  • 判断 year 的奇偶性，确定是寻找山谷还是山峰。
  • 遍历链表（从第二个到倒数第二个元素），找到所有符合条件的元素，将其迭代器存入 to_remove。
  • if (to_remove.empty())：说明本年度没有山消失，跳出循环。
  • else：遍历 to_remove 列表，从主链表中删除这些山。
  • year++。

• 输出最终的 year。

C++

#include <iostream>
#include <vector>
#include <list>
#include <numeric>

int main() {
    // 优化输入输出速度
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    // 使用 std::list (双向链表)，因为删除操作更高效
    std::list<int> mountains;
    for (int i = 0; i < n; ++i) {
        int h;
        std::cin >> h;
        mountains.push_back(h);
    }

    int year = 1;
    while (true) {
        // 如果山的总数少于3，不可能形成山谷或山峰
        if (mountains.size() < 3) {
            break;
        }

        // 存储待删除山的迭代器
        std::vector<std::list<int>::iterator> to_remove;
        // 判断是山谷年（奇数年）还是山峰年（偶数年）
        bool is_valley_year = (year % 2 == 1);

        // 遍历链表，从第二个元素到倒数第二个元素
        for (auto it = std::next(mountains.begin()); it != std::prev(mountains.end()); ++it) {
            auto prev_it = std::prev(it);
            auto next_it = std::next(it);

            if (is_valley_year) {
                // 山谷的条件: h[i] < h[i-1] && h[i] < h[i+1]
                if (*it < *prev_it && *it < *next_it) {
                    to_remove.push_back(it);
                }
            } else { // 山峰年
                // 山峰的条件: h[i] > h[i-1] && h[i] > h[i+1]
                if (*it > *prev_it && *it > *next_it) {
                    to_remove.push_back(it);
                }
            }
        }

        // 如果没有山需要被移除，则找到了答案
        if (to_remove.empty()) {
            break;
        }

        // 统一删除所有标记的山
        for (auto it : to_remove) {
            mountains.erase(it);
        }

        // 年份增加
        year++;
    }

    // 输出第一个没有山消失的年份
    std::cout << year << std::endl;

    return 0;
}

Python

import sys

def solve():
    """
    主解决函数
    """
    try:
        # 从标准输入读取数据
        n_str = sys.stdin.readline()
        if not n_str: return
        n = int(n_str)
        heights = list(map(int, sys.stdin.readline().split()))
    except (IOError, ValueError):
        return

    year = 1
    while True:
        # 山的数量不足3，无法形成山谷或山峰
        if len(heights) < 3:
            break

        # 待删除山的索引列表
        to_remove_indices = []
        is_valley_year = (year % 2 == 1)

        # 遍历所有可能的山谷或山峰（排除首尾）
        for i in range(1, len(heights) - 1):
            h_prev = heights[i-1]
            h_curr = heights[i]
            h_next = heights[i+1]

            if is_valley_year:
                # 检查是否为山谷
                if h_curr < h_prev and h_curr < h_next:
                    to_remove_indices.append(i)
            else: # 山峰年
                # 检查是否为山峰
                if h_curr > h_prev and h_curr > h_next:
                    to_remove_indices.append(i)

        # 如果没有山需要移除，当前年份就是答案
        if not to_remove_indices:
            break

        # 为了安全地删除元素，我们从后往前删除，这样不会影响前面元素的索引
        for i in reversed(to_remove_indices):
            del heights[i]
        
        # 另一种方法：通过构建一个新列表来完成删除，对于Python来说通常也足够快
        # survivors = []
        # remove_set = set(to_remove_indices)
        # for i, h in enumerate(heights):
        #     if i not in remove_set:
        #         survivors.append(h)
        # heights = survivors

        year += 1

    # 输出第一个没有山消失的年份
    print(year)

if __name__ == "__main__":
    solve()

Java

import java.util.Scanner;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        // 使用 LinkedList，因为它在删除中间元素时比 ArrayList 更高效
        LinkedList<Integer> mountains = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            mountains.add(scanner.nextInt());
        }

        int year = 1;
        while (true) {
            // 山的数量不足3，无法形成山谷或山峰
            if (mountains.size() < 3) {
                break;
            }

            // 存储待删除山的索引
            List<Integer> toRemoveIndices = new ArrayList<>();
            boolean isValleyYear = (year % 2 == 1);
            
            // 遍历链表，找出所有要删除的山
            // 从索引1开始，到 size-2 结束
            for (int i = 1; i < mountains.size() - 1; i++) {
                int prevHeight = mountains.get(i - 1);
                int currentHeight = mountains.get(i);
                int nextHeight = mountains.get(i + 1);

                if (isValleyYear) {
                    // 检查是否为山谷
                    if (currentHeight < prevHeight && currentHeight < nextHeight) {
                        toRemoveIndices.add(i);
                    }
                } else { // 山峰年
                    // 检查是否为山峰
                    if (currentHeight > prevHeight && currentHeight > nextHeight) {
                        toRemoveIndices.add(i);
                    }
                }
            }

            // 如果没有山需要移除，则当前年份就是答案
            if (toRemoveIndices.isEmpty()) {
                break;
            }

            // 从后往前删除，避免索引变化导致错误
            for (int i = toRemoveIndices.size() - 1; i >= 0; i--) {
                // toRemoveIndices.get(i) 返回的是要删除的原始索引
                int indexToRemove = toRemoveIndices.get(i);
                mountains.remove(indexToRemove);
            }

            year++;
        }

        // 输出第一个没有山消失的年份
        System.out.println(year);
        scanner.close();
    }
}

题目内容

Z 市以奇山秀林闻名世界。这里一共有 $n$ 座山排成一排，从左向右编号依次为 $1,2,…,n$ ，其中第 $i$ 座山的高度记为 $a_i$ ；

每座山的高度互不相同。如果第 $i(2≤i≤n-1)$ 座山的高度满足严格小于左右相邻的两座山，则第 $i$ 座山被称为山谷；

若满足严格大于左右相邻的两座山，则被称为山峰。由于神秘的地壳运动，每年山谷和山峰会轮流全部消失。若某一年所有山谷同时消失，下一年则是所有山峰同时消失。山的消失实际上是和相邻的山融为了一体，第 $i$ 座山消失后，第 $i-1$ 座山与第 $i+1$ 座山视为相邻(如果两座山均存在的话)。

假设今年是第一年，轮到山谷消失，小铭想知道第一次没有山消失是在第几年?

输入描述

输入第一行有一个正整数 $n(1≤n≤10^5)$ ，表示山的个数;

第二行有 $n$ 个正整数 $a_1,a_2,…,a_n(1≤a_i≤10^9)$，表示每座山的高度。

输出描述

输出一个正整数，表示第一个没有山消失的年份。

样例1

输入

6
5 7 1 2 8 3

输出

4

说明

第一年，山谷消失，第三座山是山谷，消失后数组变为 $[5$ $7$ $2$ $8$ $3$ ];

第二年，山峰消失，第二座山、第四座山是山峰，消失后数组变为 $[5$ $2$ $3$ ];

第三年，山谷消失，第二座山是山谷，消失后数组变为 $[5$ $3$]。

第四年，山峰消失，没有山峰，没有山消失。

注意，即使下一年有山谷消失，答案也应输出 $4$ ，第一个没有山消失的年份。