中山做网站建设联系电话,国家高新技术企业图片,北京网站设计精选柚v米科技,中小企业网上申报系统题目背景 无 题目描述 为了检测生产流水线上总共N件产品的质量#xff0c;我们首先给每一件产品打一个分数A表示其品质#xff0c;然后统计前M件产品中质量最差的产品的分值Q[m] min{A1, A2, ... Am}#xff0c;以及第2至第M 1件的Q[m 1], Q[m 2] ... 最后统计第N - M …题目背景 无 题目描述 为了检测生产流水线上总共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 ab?b:a;}
void rmq_init()
{for(int i1;in;i) minv[i][0]a[i];int logn(int)(log((double)n)/log(2.0));for(int j1;j20;j){for(int i1;in;i)if(i(1j)-1n) 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-l1))/log(2.0));return min(minv[l][logn],minv[r-(1logn)1][logn]);
}
int main(int argc,char *argv[])
{scanf(%d%d,n,m);for(int i1;in;i)scanf(%d,a[i]);rmq_init();for(int i1;in-m1;i) printf(%d\n,rmq(i,im-1));return 0;
} 转载于:https://www.cnblogs.com/ruojisun/p/7718571.html
