2026年 北马其顿编程竞赛 (Macedonian programming contests 2026)

赛事等级： 社区与地区选拔赛 (Community and Regional competition)
内容类型： 竞赛题目 (Competition tasks)

题目名称：选举活动 (Пак изборна кампања)

题目描述

选举即将举行。在接下来的 $N$ 天竞选活动中，执政党每天都将组织一场集会。由于组织得力，他们已经预知了每场集会参加的人数。

一位外国贵宾将在竞选期间访问马其顿，逗留时间为 $K$ 天。执政党希望确定：对于任意连续的 $K$ 天，如果客人在该时间段内访问，他所能见到的单场集会最大人数是多少？

你的任务是：计算出每一个长度为 $K$ 的连续时间段内的最大人数。

输入格式

• 第一行包含一个整数 $N$（竞选活动的总天数，$1 \le N \le 1,000,000$）。
• 第二行包含一个整数 $K$（客人的逗留天数，$1 \le K \le N$）。
• 第三行包含由 $N$ 个非负整数组成的序列 $A$，其中 $A_i$ 代表第 $i$ 天集会的人数（$0 \le A_i \le 10^9$）。

注意： 对于 40% 的测试点，$N < 1,500$。

输出格式

• 输出一个由 $N - K + 1$ 个整数组成的序列 $B$，其中每个元素 $B_i$ 是对应长度为 $K$ 的窗口内的最大值。

限制条件

• 时间限制： 500 毫秒
• 内存限制： 64 MB

样例说明

输入：

9
3
8 1 4 3 2 7 6 9 5

输出：

8 4 4 7 7 9 9

解释（逐个周期分析）： 窗口从左向右滑动，每次取连续的 3 个数并找出其中的最大值：

1. 周期 1: [8, 1, 4] 最大值: 8
2. 周期 2: [1, 4, 3] 最大值: 4
3. 周期 3: [4, 3, 2] 最大值: 4
4. 周期 4: [3, 2, 7] 最大值: 7
5. 周期 5: [2, 7, 6] 最大值: 7
6. 周期 6: [7, 6, 9] 最大值: 9
7. 周期 7: [6, 9, 5] 最大值: 9

算法提示

这是一个经典的**滑动窗口最大值（Sliding Window Maximum）**问题。

1. 暴力法 ($O(N \cdot K)$)：对于每个起点，遍历 $K$ 个数找最大值。这可以通过 40% 的测试点，但对于 $N=10^6$ 的数据会超时。
2. 单调队列 ($O(N)$)：使用一个双端队列（Deque）来维护窗口内可能成为最大值的候选下标。
   • 队列中的元素按数值从大到小排列。
   • 每次窗口滑动时，弹出左侧已过期的下标，同时从右侧弹出所有比当前新加入元素小的元素。
   • 队列头部的元素即为当前窗口的最大值。
3. 内存提示：由于 $N$ 较大且内存限制为 64MB，建议使用高效的数据结构，避免过多的额外内存开销。

版权信息

• 项目： Macedonian Programming Contests 2026
• 赛事： Community and Regional competition
• 版权方： Zidruženije na informatičari na Makedonija (ZIM / 北马其顿计算机科学家协会)