小蓝有一个序列a[1], a[2]. .... a[n]. 给定一个正整数k，请问对于每一个1到n之间的序号i，a[i-k], a[i-k+1].... a[i+k]这2k+1个数中的最小值是多少?当某个下标超过1到n的范围时，数不存在，求最小值时只取存在的那些值，单调队列求解

对于每一个1到n之间的序号i，a[i-k], a[i-k+1].... a[i+k]这2k+1个数中的最小值可以通过单调队列求解。具体方法如下：

1. 初始化一个单调队列q，将a[1]~a[k]的下标依次加入队列中。

2. 从i=k+1开始遍历序列a，每次将a[i]的下标加入队列中。

3. 如果队列头部的下标已经小于i-k，则将其弹出队列。

4. 队列头部的下标对应的数就是a[i-k], a[i-k+1].... a[i+k]这2k+1个数中的最小值。

5. 将这个最小值记录下来，并将a[i]的下标加入队列中。

6. 遍历完整个序列后，最小值的记录就是答案。

代码实现如下：

int n, k;
int a[MAXN];
deque<int> q;

for (int i = 1; i <= n; i++) {
if (!q.empty() && q.front() < i - k) q.pop_front();
while (!q.empty() && a[q.back()] >= a[i]) q.pop_back();
q.push_back(i);
if (i >= k) printf("%d ", a[q.front()]);
}

相关问题

小蓝有一个序列 a[1], a[2], ..., a[n]，每次可以交换相邻的两个元素，代价为两个元素中较大的那个。 请问，要通过交换将序列变为从小到大递增的序列，总代价最少为多少？

要通过交换将序列变为从小到大递增的序列，总代价最少为多少？

假设原序列为 a[1], a[2], ..., a[n]，我们可以使用冒泡排序的思想，每次将最大的元素交换到它应该在的位置上，直到整个序列有序。

具体地，我们从左到右遍历序列，如果当前元素比它右边的元素大，就交换它们的位置。这样一轮下来，最大的元素就会被交换到最右边的位置上。然后我们再从左到右遍历序列，除了最右边已经排好序的元素，对剩下的元素重复上述操作，直到整个序列有序。

在这个过程中，每次交换的代价为两个元素中较大的那个，因此总代价为所有交换代价的和。由于每次交换都会将一个元素放到它应该在的位置上，因此最多需要进行 n-1 轮交换，每轮交换的代价最多为序列中最大的元素。因此，总代价最多为 n(n-1)/2 乘以序列中最大的元素。

综上所述，要通过交换将序列变为从小到大递增的序列，总代价最少为 n(n-1)/2 乘以序列中最大的元素。

问题描述 小蓝有一个序列 a[1], a[2], ..., a[n]。 给定一个正整数 k，请问对于每一个 1 到 n 之间的序号 i，a[i-k], a[i-k+1], ..., a[i+k] 这 2k+1 个数中的最小值是多少？当某个下标超过 1 到 n 的范围时，数不存在，求最小值时只取存在的那些值。 输入格式 输入的第一行包含一整数 n。 第二行包含 n 个整数，分别表示 a[1], a[2], ..., a[n]。 第三行包含一个整数 k 。 输出格式 输出一行，包含 n 个整数，分别表示对于每个序号求得的最小值。 样例输入 5 5 2 7 4 3 1 样例输出 2 2 2 3 3 请用Python代码实现

n = int(input())
a = list(map(int, input().split()))
k = int(input())

# 初始化双端队列
q = []
for i in range(k):
    while q and a[i] <= a[q[-1]]:
        q.pop()
    q.append(i)

# 处理剩余元素
res = [a[q[0]]]
for i in range(k, n):
    # 判断队首元素是否在窗口内
    if q and q[0] <= i - k:
        q.pop(0)
    # 维护单调性
    while q and a[i] <= a[q[-1]]:
        q.pop()
    q.append(i)
    res.append(a[q[0]])

print(*res)