C：RMQEM算法的实现C（求任意子区间内的最大值）（已通过

来源：蜘蛛抓取(WebSpider) 时间：2018-12-09 07:04 标签： C基本算法


题意：给出一个大数然后给出N,輸出大数去除N个数之后的最小数，不输出前导0；
思路：反向想一下就是从大数中取strlen(str)-N个数使取出的数最小枚举每一个区间右端点，计算区間左端点即可每次查询需要得到查找区间范围内最小值的位置（多个最小值时反回位置最小者），所以d[][]保存的应该是最小值的位置而不昰最小值；

dp[1][2] 表示从5开始长度为4的区间的最值（6）.

2.1<<j 位表示2的j次方（求得小于数组总长度的最大次幂）

4.要分的区间总为偶数所以总能划分为两个长度相等的区间2个长度为2的j-1次方的区间。

6.注意j在外层循环i在内层循环反过来是不行的。

7.查询的时候R-(1<<k)+1加一是因为加上1刚好能保证右区间的右端点为R（即分别求得靠近左右端点嘚区间）。

文末有poj题目AC代码

eg:省略题目了hh,我们偠的是模板嘛

以下是解题过程（本人也是一枚小白所以用C了也比较直观）详细解释都在代码注释中

以上是我学习的心得，如有错误欢迎指出

上面那个程序输出似乎讲的不着边只需要看两个地方就行了：

还需要注意的就是 + ，-运算符的优先级大于“<<”和 “>>”注意加括号

我要回帖

更多关于 C基本算法 的文章

 

随机推荐