51nod——1174 区间中最大的数
程序员文章站
2022-05-17 15:38:36
题目链接 给出一个有N个数的序列,编号0 - N - 1。进行Q次查询,查询编号i至j的所有数中,最大的数是多少。 例如: 1 7 6 3 1。i = 1, j = 3,对应的数为7 6 3,最大的数为7。(该问题也被称为RMQ问题) 输入 输出 输入样例 输出样例 Sparse Table解决Ra ......
给出一个有n个数的序列,编号0 - n - 1。进行q次查询,查询编号i至j的所有数中,最大的数是多少。
例如: 1 7 6 3 1。i = 1, j = 3,对应的数为7 6 3,最大的数为7。(该问题也被称为rmq问题)
输入
第1行:1个数n,表示序列的长度。(2 <= n <= 10000) 第2 - n + 1行:每行1个数,对应序列中的元素。(0 <= s[i] <= 10^9) 第n + 2行:1个数q,表示查询的数量。(2 <= q <= 10000) 第n + 3 - n + q + 2行:每行2个数,对应查询的起始编号i和结束编号j。(0 <= i <= j <= n - 1)
输出
共q行,对应每一个查询区间的最大值。
输入样例
5 1 7 6 3 1 3 0 1 1 3 3 4
输出样例
7 7 3
sparse table解决range minimum/maximum query学习参考博客
分析
st用dp o(nlogn)预处理 ,o(1)查询。
设a[i]是要求区间最值的数列,rmq[i, j]表示从第i个数起连续2^j个数中的最大值。
例如:
a数列为:3 2 4 5 6 8 1 2 9 7
rmq[1,0]表示第1个数起,长度为2^0=1的最大值,其实就是3这个数。同理 rmq[1,1] = max(3,2) = 3, rmq[1,2]=max(3,2,4,5) = 5,rmq[1,3] = max(3,2,4,5,6,8,1,2) = 8;
且[i,0]就等于a[i]。
状态转移方程rmq[i, j]=max(rmq[i,j-1], rmq[i + 2^(j-1),j-1])。
1 #include <iostream> 2 #include <cstdio> 3 #include <cmath> 4 #include <cstring> 5 #define maxn 10005 6 using namespace std; 7 8 int a[maxn],rmq[maxn][15]; 9 10 void rmq_init(int n){ 11 for(int i = 0; i < n; ++i) rmq[i][0] = a[i]; 12 for(int j = 1; (1<<j) <= n; ++j) 13 for(int i = 0; i + (1<<j) - 1 < n; ++i) 14 rmq[i][j] = max(rmq[i][j-1], rmq[i + (1<<(j-1))][j-1]); 15 } 16 17 int find(int l, int r){ 18 int k = 0; 19 while((1<<(k+1)) <= r-l+1) k++; 20 return max(rmq[l][k], rmq[r-(1<<k)+1][k]); 21 } 22 23 int main(){ 24 int n,q,l,r; 25 while(cin>>n){ 26 memset(rmq, 0, sizeof(rmq)); 27 for(int i=0;i<n;++i) cin>>a[i]; 28 rmq_init(n); 29 cin>>q; 30 while(q--){ 31 cin>>l>>r; 32 cout<<find(l,r)<<endl; 33 } 34 } 35 return 0; 36 }
上一篇: ASP把网页中的电话号码生成图片的代码
下一篇: 多重背包模板
推荐阅读
-
51nod——1174 区间中最大的数
-
IN查询时出现ORA-01795:列表中的最大表达式数为1000(问题解决)
-
ORA-01795: 列表中的最大表达式数为 1000实例解决
-
C题解:有一棵树,一开始每个点有一个初始值,每一个点的新数为它到树顶的路径中的所有数,去掉一个数后的最大公因数中的最大值
-
docker中修改mysql最大连接数及配置文件的实现
-
Docker容器中的MySQL最大连接数被限制为214的问题解决方法
-
PHP 查找数值数组中不重复最大和最小的10个数
-
加大MYSQL中的最大连接数的两种方法
-
php实现用三元运算符求三个数中的最大值,最小值
-
加大MYSQL中的最大连接数的两种方法