洛谷P2251 质量检测

题目描述

为了检测生产流水线上总共 $N$ 件产品的质量，我们首先给每一件产品打一个分数 $A$ 表示其品质，然后统计前 $M$ 件产品中质量最差的产品的分值 $Q[m] = min\{A_1, A_2, ... A_m\}$，以及第 2 至第 $M + 1$ 件的 $Q[m + 1], Q[m + 2] $... 最后统计第 $N - M + 1$ 至第 $N$ 件的 $Q[n]$。根据 $Q$ 再做进一步评估。

请你尽快求出 $Q$ 序列。

输入格式

输入共两行。

第一行共两个数 $N$、$M$，由空格隔开。含义如前述。

第二行共 $N$ 个数，表示 $N$ 件产品的质量。

输出格式

输出共 $N - M + 1$ 行。

第 1 至 $N - M + 1$ 行每行一个数，第 $i$ 行的数 $Q[i + M - 1]$。含义如前述。

样例 #1

样例输入 #1

10 4
16 5 6 9 5 13 14 20 8 12

### 样例输出 #1

5
5
5
5
5
8
8

提示

[数据范围]

30%的数据，$N \le 1000$

100%的数据，$N \le 100000$

100%的数据，$M \le N, A \le 1 000 000$

题解

#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, m, t, top, Q[1000010];

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