【RMQ算法】:用于当数组过于庞大的时候,查询区间的最大(最小)值。
时间复杂度:O(nlogn),主要时间发费在预处理上,查询只要O(1)。
- 描述
-
南将军统率着N个士兵,士兵分别编号为1~N,南将军经常爱拿某一段编号内杀敌数最高的人与杀敌数最低的人进行比较,计算出两个人的杀敌数差值,用这种方法一方面能鼓舞杀敌数高的人,另一方面也算是批评杀敌数低的人,起到了很好的效果。
所以,南将军经常问军师小工第i号士兵到第j号士兵中,杀敌数最高的人与杀敌数最低的人之间军功差值是多少。
现在,请你写一个程序,帮小工回答南将军每次的询问吧。
注意,南将军可能询问很多次。
- 输入
- 只有一组测试数据
第一行是两个整数N,Q,其中N表示士兵的总数。Q表示南将军询问的次数。(1<N<=100000,1<Q<=1000000)
随后的一行有N个整数Vi(0<=Vi<100000000),分别表示每个人的杀敌数。
再之后的Q行,每行有两个正正数m,n,表示南将军询问的是第m号士兵到第n号士兵。 - 输出
- 对于每次询问,输出第m号士兵到第n号士兵之间所有士兵杀敌数的最大值与最小值的差。
- 样例输入
-
5 2
1 2 6 9 3
1 2
2 4 - 样例输出
- 1
- 7
- 代码如下:(数据过大的时候建议用scanf输入,用cin有可能会时间超限)。
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std; const int N = ;
int maxsum[][N], minsum[][N]; void RMQ(int num) //预处理->O(nlogn)
{
for(int i = ; i != ; ++i)
for(int j = ; j <= num; ++j)
if(j + ( << i) - <= num)
{
maxsum[i][j] = max(maxsum[i - ][j], maxsum[i - ][j + ( << i >> )]);
minsum[i][j] = min(minsum[i - ][j], minsum[i - ][j + ( << i >> )]);
}
} int main()
{
int num, query;
int src, des;
scanf("%d %d", &num, &query);
for(int i = ; i <= num; ++i) //输入信息处理
{
scanf("%d", &maxsum[][i]);
minsum[][i] = maxsum[][i];
}
RMQ(num);
while(query--) //O(1)查询
{
scanf("%d %d", &src, &des);
int k = (int)(log(des - src + 1.0) / log(2.0));
int maxres = max(maxsum[k][src], maxsum[k][des - ( << k) + ]);
int minres = min(minsum[k][src], minsum[k][des - ( << k) + ]);
printf("%d\n", maxres - minres);
}
return ;
}
ACM题目————士兵杀敌(三)的更多相关文章
-
ACM题目————士兵杀敌(四)
描述 南将军麾下有百万精兵,现已知共有M个士兵,编号为1~M,每次有任务的时候,总会有一批编号连在一起人请战(编号相近的 人经常在一块,相互之间比较熟悉),最终他们获得的军功,也将会平分到每个人身上, ...
-
士兵杀敌 三 --- O( 1 ) 的时间复杂度 .
一看就是 十分简单的 题 , 然后上去开始无脑程序 超时~~~ 感觉时间复杂度 , 已经很低了 , 但是并没有什么卵用 . #include<stdio.h> #in ...
-
NYOJ 119 士兵杀敌(三) RMQ ST
NYOJ 119 士兵杀敌(三) RMQ ST 题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=119 思路: ST在线 预处理O(nlog ...
-
nyoj 119士兵杀敌(三)(线段树区间最值查询,RMQ算法)
题目119 题目信息 执行结果 本题排行 讨论区 士兵杀敌(三) 时间限制:2000 ms | 内存限制:65535 KB 难度:5 描写叙述 南将军统率着N个士兵,士兵分别编号为1~N,南将军常 ...
-
士兵杀敌(三)_RMQ(区间最值查询)
士兵杀敌(三) 时间限制:2000 ms | 内存限制:65535 KB 难度:5 描述 南将军统率着N个士兵,士兵分别编号为1~N,南将军经常爱拿某一段编号内杀敌数最高的人与杀敌数最低的人进 ...
-
nyoj 119 士兵杀敌(三)(RMQ)
士兵杀敌(三) 时间限制:2000 ms | 内存限制:65535 KB 难度:5 描述 南将军统率着N个士兵,士兵分别编号为1~N,南将军经常爱拿某一段编号内杀敌数最高的人与杀敌数最低的人进 ...
-
nyoj 119 士兵杀敌(三)【线段树区间最大值最小值差】
士兵杀敌(三) 时间限制:2000 ms | 内存限制:65535 KB 难度:5 描述 南将军统率着N个士兵,士兵分别编号为1~N,南将军经常爱拿某一段编号内杀敌数最高的人与杀敌数最低的人进 ...
-
NYOJ 119 士兵杀敌(三) (线段树)
题目链接 描述 南将军统率着N个士兵,士兵分别编号为1~N,南将军经常爱拿某一段编号内杀敌数最高的人与杀敌数最低的人进行比较,计算出两个人的杀敌数差值,用这种方法一方面能鼓舞杀敌数高的人,另一方面也算 ...
-
nyoj119 士兵杀敌(三)
士兵杀敌(三) 时间限制:2000 ms | 内存限制:65535 KB 难度:5 描述 南将军统率着N个士兵,士兵分别编号为1~N,南将军经常爱拿某一段编号内杀敌数最高的人与杀敌数最低的人进 ...
随机推荐
-
Win10安装程序出现error code 2502 2503
在Win10中,在安装msi安装包的时候常常会出现代码为2502.2503的错误.其实这种错误是由于安装权限不足造成的,可以这种msi的安装包不像其他exe的安装程序,在安装包上点击"右键& ...
-
分部方法 partial
当有如下这样类似的情况出现的时候,可以有更好的优化方式来处理,那就是分部方法 class PartOld { string name; public virtual void OnChangeName ...
-
java.lang.Long cannot be cast to java.lang.Integer解决办法
情景: mybatis连接oracle 报错: 测试增的时候,报错 Java.lang.Long cannot be cast to java.lang.Integer:删改没有报错. 排查过程: ...
-
U3D C#脚本的生命周期
MonoBehaviour是每个脚本的基类. 每个Javascript脚本自动继承MonoBehaviour,使用C#或Boo时,需要显式继承MonoBehaviour. 一开始实例化,直到结束实例被 ...
-
【转】Android辅助功能AccessibilityService自动全选择文字粘贴模拟输入
网上找了很久AccessibilityService全选文字的方法,一直没找到,自己研究了半天,分享出来. /** * 输入文本 */ public void inputText(List<St ...
-
每天CSS学习之border-spacing
border-spacing是CSS2的一个属性.其作用是规定表格的相邻单元格边框之间的距离.如果表格的border-collapse属性值为collapse时,border-spacing设置无效. ...
-
Maven部署dao工程到私服上——(十三)
1.修改settings.xml 需要在客户端即(部署dao工程)的电脑上配置 maven环境,并修改 settings.xml 文件,配置连接私服的用户和密码 . 此用户名和密码用于私服校验,因为私 ...
-
VS2008中MFC对话框界面编程Caption中文乱码的解决办法
文章转载自http://blog.csdn.net/ajioy/article/details/6877646 最近在使用VS2008编写一个基于对话框的程序时,在对话框中添加Static控件,编写其 ...
-
<;编程之美>;经典面试题:求二叉树节点的最大距离(我的解法,最容易理解的版本?)
题目介绍: 如果把二叉树看成一个图,父子节点之间的连线看成是双向的,我们姑且定义"距离"为两个节点之间的个数. 写一个程序求一棵二叉树中相距最远的两个节点之间的距离. 如下图所示, ...
-
进度条算法 progressBar
; ;var maxNum=int.MaxValue; progressBar.Maximum =maxNum; progressBar.Minimum = ; progressBar.Value = ...