P2251 质量检测
题目背景
无
题目描述
为了检测生产流水线上总共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表
几乎就是ST表的模板题
先预处理出跳的步数小于等于m的2^k步
然后自己处理处LG函数
目的就是为了知道2^k<=m中
k的最大值是多少
如果刚好2^k==m那就不需要继续了
如果不刚好
那就记录最大的那个枚举到的k
就是LG[m]的值
然后按照板子输出
区间最小值就好了
区间怎么算呢？
起点是i很显然
终点是i + m - 1
这样起点和重点就知道啦
所以这个区间的最小值就是
min(f[i][LG[m]],f[i + m - 1 - (1 << LG[m]) + 1][LG[m]]);
【完整代码】
#include<iostream>
#include<cstdio>
using namespace std;
const int Max = 100005;
int a[Max];
int f[Max][18];
int LG[Max];
int main()
{
int n,m;
cin >> n >> m;
for(register int i = 1;i <= n;++ i)
cin >> a[i],f[i][0] = a[i];
for(register int j = 1;(1 << j) <= m;++ j)
for(register int i = 1;i + (1 << j) - 1 <= n;++ i)
f[i][j] = min(f[i][j - 1],f[i + (1 << j - 1)][j - 1]);
int acioi = 0;
for(register int i = 1;(1 << i) <= m;++ i)
LG[1 << i] = i,acioi = i;
if(LG[m] == 0)
LG[m] = acioi;
for(register int i = 1;i <= n - m + 1;++ i)
printf("%d\n",min(f[i][LG[m]],f[i + m - 1 - (1 << LG[m]) + 1][LG[m]]));
return 0;
}