洛谷P2032 扫描

题目描述

有一个 $1 \times n$ 的矩阵，有 $n$ 个整数。

现在给你一个可以盖住连续 $k$ 个数的木板。

一开始木板盖住了矩阵的第 $1 \sim k$ 个数，每次将木板向右移动一个单位，直到右端与第 $n$ 个数重合。

每次移动前输出被覆盖住的数字中最大的数是多少。

输入格式

第一行两个整数 $n,k$，表示共有 $n$ 个数，木板可以盖住 $k$ 个数。

第二行 $n$ 个整数，表示矩阵中的元素。

输出格式

共 $n - k + 1$ 行，每行一个整数。

第 $i$ 行表示第 $i \sim i + k - 1$ 个数中最大值是多少。

样例 #1

样例输入 #1

5 3
1 5 3 4 2

样例输出 #1

5
5
4

提示

对于 $20\%$ 的数据，$1 \leq k \leq n \leq 10^3$。

对于 $50\%$ 的数据，$1 \leq k \leq n \leq 10^4$。

对于 $100\%$ 的数据，$1 \leq k \leq n \leq 2 \times 10^6$，矩阵中的元素大小不超过 $10^4$ 并且均为正整数。

题解

#include <bits/stdc++.h>
using namespace std;

struct node {
    int num, z;
    node(int x, int y) {
        num = x;
        z = y;
    }
    bool operator<(const node x) const {
        return (z < x.z) || (z == x.z && num < x.num);
    }
};

priority_queue<node> q;
int n, k, top, a[2000010], ans[2000010];

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        scanf("%d", a + i);
    for (int i = 1; i <= k; i++)
        q.push(node(i, a[i]));
    ans[++top] = q.top().z;
    for (int i = k + 1; i <= n; i++) {
        q.push(node(i, a[i]));
        while (i - q.top().num >= k) q.pop();
        ans[++top] = q.top().z;
    }
    for (int i = 1; i <= top; i++) printf("%d\n", ans[i]);
    return 0;
}