洛谷 P2251 质量检测

题目描述

为了检测生产流水线上总共 N 件产品的质量，我们首先给每一件产品打一个分数 A 表示其品质，然后统计前 M 件产品中质量最差的产品的分值 Qm​=min{A1​,A2​,⋯,Am​}，以及第 2 至第 M+1 件的 Qm+1​，Qm+2​…… 最后统计第 N−M+1 至第 N 件的 Qn​。根据 Q 再做进一步评估。

请你尽快求出 Q 序列。

输入格式

输入共两行。

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

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

输出格式

输出共 N−M+1 行。

第 1 至 N−M+1 行每行一个数，第 i 行的数 Qi+M−1​。含义如前述。

输入输出样例

输入 #1复制

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

输出 #1复制

5 5 5 5 5 8 8

说明/提示

[数据范围]

对于 30% 的数据，N≤1000。

对于 100% 的数据，M≤N≤105,Ai​≤106。

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int a[N]; int n,m; int main() { cin>>n>>m; for(int i=1;i<=n;i++) { cin>>a[i]; } deque<int> q; for(int i=1;i<=n;i++) { while(q.size()&&a[q.back()]>=a[i]) q.pop_back(); q.push_back(i); if(q.back()-q.front()+1>m) q.pop_front(); if(i>=m) cout<<a[q.front()]<<endl; } return 0; }