求pat甲级题考点(转载各个大佬)帮忙解决下面这两道题


    

 
题目大意:每条绳子可以对折形荿环跟另一条同样对折成环的绳子连接成新的一条绳子这样产生的新绳子就是原来两条绳子长度之和的一半;形成的新绳子又继续跟其怹绳子以同样的方法连接成另一条新绳;给出一个整数序列(绳子的长度),求能够连接成的最长的绳子的长度
思路:将数列从小到大排列,尽量先对折长度较小的绳子
 

版权声明:本文为博主原创文章未经博主允许不得转载。 /qq_/article/details/

本题解法很多首先介绍划分树解法。本题是划分树典型题型代码如下:

//当前序列的左右端点、层数 //查询区间第K大的数,[L,R]是大区间[l,r]是要查询的小区间 //在1~n位置中找到s~t位置内第k大的数

第二种解法是基于平方分割法的RMQ,怎么说呢用这种方法时间复杂度处于过与不过的边缘,我尽量减少了函数的调用能用嘚优化基本都开了,估计就差自己写读入函数了下面的代码有几率AC:

我要回帖

更多关于 PAT甲级题考点(转载各个大佬) 的文章

 

随机推荐