牛王争霸,沐猴而冠造句,发烧38度怎么办
南将军统率着n个士兵,士兵分别编号为1~n,南将军经常爱拿某一段编号内杀敌数最高的人与杀敌数最低的人进行比较,计算出两个人的杀敌数差值,用这种方法一方面能鼓舞杀敌数高的人,另一方面也算是批评杀敌数低的人,起到了很好的效果。
所以,南将军经常问军师小工第i号士兵到第j号士兵中,杀敌数最高的人与杀敌数最低的人之间军功差值是多少。
现在,请你写一个程序,帮小工回答南将军每次的询问吧。
注意,南将军可能询问很多次。
5 2 1 2 6 9 3 1 2 2 4
1 7
看到这样的题就想到线段树 唉 还是知道的算法太少了
第一次线段树还超时了(粗心 忘记写return 了)
还可以用rmq算法(比线段树快多了。。) 。百度的。。。。
线段树 1836ms 险过。。。
#include #include using namespace std; struct node { int left,right; int max_num,min_num; }tree[100000*4]; void build(int left,int right,int root) { tree[root].left=left; tree[root].right=right; if(left==right) { scanf("%d",&tree[root].max_num); tree[root].min_num=tree[root].max_num; return ; } else { int mid=(left+right)/2; build(left,mid,root*2); build(mid+1,right,root*2+1); tree[root].max_num=max(tree[root*2].max_num,tree[root*2+1].max_num); tree[root].min_num=min(tree[root*2].min_num,tree[root*2+1].min_num); } } void search(int l,int r,int root,int &c,int &d) { if(tree[root].left==l&&tree[root].right==r) { c=tree[root].max_num; d=tree[root].min_num; return ; } int mid=(tree[root].left+tree[root].right)/2; if(mid>=r) search(l,r,root*2,c,d); else if(mid
rmq算法 976ms 节省了近一倍的事件。如果不懂rmq (range minimum/maximum query)算法,看下文:
#include #include #include using namespace std; int min_num[100005][20]; int max_num[100005][20]; int n,k; void rmq() { for(int i=1;i<20;i++) { for(int j=1;j<=n;j++) { if(j+(1<
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论