題目背景

無

題目描述

為了檢測生產流水線上總共N件產品的質量，我們首先給每一件產品打一個分數A表示其品質，然后統計前M件產品中質量最差的產品的分值Q[m] = min{A1, A2, ... Am}，以及第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：
10 4 16 5 6 9 5 13 14 20 8 12 輸出樣例#1：
5 5 5 5 5 8 8

說明

[數據范圍]

30%的數據，N <= 1000

100%的數據，N <= 100000

100%的數據，M <= N, A <= 1 000 000

?

?

果ST表

語文不好是硬傷，讀題讀好久

屠龍寶刀點擊就送

#include <cstdio> #include <cmath> #define N 100005int n,m,a[N],minv[N][20]; inline int min(int a,int b) {return a>b?b:a;} void rmq_init() {for(int i=1;i<=n;++i) minv[i][0]=a[i];int logn=(int)(log((double)n)/log(2.0));for(int j=1;j<=20;++j){for(int i=1;i<=n;++i)if(i+(1<<j)-1<=n) minv[i][j]=min(minv[i][j-1],minv[i+(1<<(j-1))][j-1]);} } inline int rmq(int l,int r) {int logn=(int)(log((double)(r-l+1))/log(2.0));return min(minv[l][logn],minv[r-(1<<logn)+1][logn]); } int main(int argc,char *argv[]) {scanf("%d%d",&n,&m);for(int i=1;i<=n;++i)scanf("%d",&a[i]);rmq_init();for(int i=1;i<=n-m+1;++i) printf("%d\n",rmq(i,i+m-1));return 0; }

?

轉載于:https://www.cnblogs.com/ruojisun/p/7718571.html

總結

以上是生活随笔為你收集整理的洛谷 P2251 质量检测的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。