首页 > 其他 > 详细

P3381: [Usaco2004 Open]Cave Cows 2 洞穴里的牛之二

时间:2015-09-22 22:03:08      阅读:339      评论:0      收藏:0      [点我收藏+]

这题。。思维上远没有上一题复杂,是一个裸的RMQ。。利用倍增就可以解决了。

技术分享
 1 var n,q,i,j,f,t,c:longint;
 2 a:array[0..20,0..25001] of longint;
 3 function min(a,b:longint):longint;
 4 begin
 5   if a>b then exit(b)
 6     else exit(a);
 7 end;
 8 begin
 9   readln(n,q);
10   for i:=1 to n do
11     readln(a[0,i]);
12   for i:=1 to trunc(ln(n)/ln(2))+1 do
13     for j:=1 to n-(1 shl i)+1 do
14       a[i,j]:=min(a[i-1,j],a[i-1,j+(1 shl (i-1))]);
15   for i:=1 to q do
16     begin
17       readln(f,t);
18       c:=trunc(ln(t-f+1)/ln(2));
19       writeln(min(a[c,f],a[c,t-(1 shl c)+1]));
20     end;
21 end.
View Code

 (转载请注明出处:http://www.cnblogs.com/Kalenda/)

P3381: [Usaco2004 Open]Cave Cows 2 洞穴里的牛之二

原文:http://www.cnblogs.com/Kalenda/p/4830520.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!