【二分与前缀和】python例题详解

这篇具有很好参考价值的文章主要介绍了【二分与前缀和】python例题详解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

文章目录

1、数的范围

2、数的三次方根

3、前缀和

4、子矩阵的和

5、机器人跳跃问题

1、数的范围

题目
给定一个按照升序排列的长度为 n 的整数数组,以及 q 个查询。对于每个查询,返回一个元素 k的起始位置和终止位置(位置从 00 开始计数)。如果数组中不存在该元素,则返回 -1 -1
输入格式
第一行包含整数 n 和 q,表示数组长度和询问个数。第二行包含 n 个整数(均在 1∼100001∼10000 范围内),表示完整数组。接下来 q 行,每行包含一个整数 k,表示一个询问元素。
输出格式
共 q 行,每行包含两个整数,表示所求元素的起始位置和终止位置。如果数组中不存在该元素,则返回 -1 -1

n,m=map(int,input().split())

a=list(map(int,input().split()))

for i in range(m):
    b=int(input())
    l,r=0,n-1
    while l<r:
        zz=(l+r)//2
        if b<=a[zz]:
            r=zz
        else: l=zz+1
        
    if a[l]==b:
        print(l,end=' ')
    else :
        print(-1,end=' ')

    l,r=0,n-1
    while l<r:
        zz=(l+r+1)>>1
        if b>=a[zz]:
            l=zz
        else: r=zz-1
    if a[l]==b:
        print(l)
    else:print(-1)
    

2、数的三次方根

题目
给定一个浮点数 n,求它的三次方根。
输入格式
共一行,包含一个浮点数 n。
输出格式
共一行,包含一个浮点数,表示问题的解。注意,结果保留 66 位小数。

l,r=-10000,10000

n=float(input())
while r>l+10**-8:
    mid=(l+r)/2
    if mid**3<=n:
        l=mid
    else: r=mid
    
print("%.6f"%r)

3、前缀和

题目
输入一个长度为 n 的整数序列。接下来再输入 m 个询问,每个询问输入一对 l,r。对于每个询问,输出原序列中从第 l个数到第 r 个数的和。
输入格式
第一行包含两个整数 n和 m。第二行包含 n 个整数,表示整数数列。接下来 m行,每行包含两个整数 l 和 r,表示一个询问的区间范围。
输出格式
共 m行,每行输出一个询问的结果。

n,m=map(int,input().split())

a=list(map(int,input().split()))

for i in range(1,n):
    a[i]+=a[i-1]

while m:
    l,r=map(int,input().split())

    if l==1:
        print(a[r-1])
    else:print(a[r-1]-a[l-2])
    
    m-=1

4、子矩阵的和

题目
输入一个 n行 m列的整数矩阵,再输入 q个询问,每个询问包含四个整数 x1,y1,x2,y2,表示一个子矩阵的左上角坐标和右下角坐标。对于每个询问输出子矩阵中所有数的和。
输入格式
第一行包含三个整数 n,m,q。接下来 n行,每行包含 m 个整数,表示整数矩阵。接下来 q行,每行包含四个整数 x1,y1,x2,y2,表示一组询问。
输出格式
共 q行,每行输出一个询问的结果。

n,m,q=map(int,input().split())
mt=[[0 for _ in range(m+1)]for __ in range(n+1)]
sm=[[0 for _ in range(m+1)]for __ in range(n+1)]
for i in range(1,n+1):
    mt[i][1:]=list(map(int,input().split()))

sm[0][0]=mt[0][0]
for i in range(1,n+1):
    for j in range(1,m+1):
        sm[i][j]=sm[i][j-1]+sm[i-1][j]+mt[i][j]-sm[i-1][j-1]

for i in range(q):
    x1,y1,x2,y2=map(int,input().split())
    print(sm[x2][y2]-sm[x2][y1-1]-sm[x1-1][y2]+sm[x1-1][y1-1])

5、机器人跳跃问题

题目
机器人正在玩一个古老的基于 DOS 的游戏。游戏中有 N+1 座建筑——从 00 到 N编号,从左到右排列。编号为 00 的建筑高度为 00 个单位,编号为 i的建筑高度为 H(i)个单位。起初,机器人在编号为 00 的建筑处。每一步,它跳到下一个(右边)建筑。假设机器人在第 k个建筑,且它现在的能量值是 E,下一步它将跳到第 k+1个建筑。如果 H(k+1)>E,那么机器人就失去 H(k+1)−E 的能量值,否则它将得到 E−H(k+1)的能量值。游戏目标是到达第 N个建筑,在这个过程中能量值不能为负数个单位。现在的问题是机器人至少以多少能量值开始游戏,才可以保证成功完成游戏?
输入格式
第一行输入整数 N。第二行是 N个空格分隔的整数,H(1),H(2),…,H(N)代表建筑物的高度。
输出格式
输出一个整数,表示所需的最少单位的初始能量值上取整后的结果。文章来源地址https://www.toymoban.com/news/detail-861256.html

n = int(input())
#l,r = 0,10**5+10

h = list(map(int,input().split()))
l,r = 0,max(h)
def check(x):
    for i in range(n):
        x+= x - h[i]
        if x < 0:
            return False
    return True
    
while l < r:
    mid = l + r >> 1
    if check(mid):
        r = mid
    else:
        l = mid + 1
print(l)

到了这里,关于【二分与前缀和】python例题详解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】浅谈数据结构-链表【思路+例题学习】

    🏆今日学习目标: 🍀学习算法-数据结构-链表 ✅创作者:贤鱼 ⏰预计时间:30分钟 🎉个人主页:贤鱼的个人主页 🔥专栏系列:算法 🍁贤鱼的个人社区,欢迎你的加入 贤鱼摆烂团 链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中

    2024年01月21日
    浏览(10)
  • 数据结构队列例题一顺序实现

    仅供个人复习使用

    2024年02月06日
    浏览(12)
  • 【数据结构】期末考试复习(考点+例题)

    线性表,栈,队列- 操作应用结果 树的构造,遍历(中序),存储,哈夫曼树,最佳二叉排序树,平衡二叉排序树, 散列(必考)快速查找,函数构造,冲突地址,平均查找长度 排序算法结果,代码(交换,比较次数,对应过程,复杂度)不考冒泡! 图的存储,遍历,最小

    2024年02月11日
    浏览(15)
  • 手撕数据结构之栈+例题

    目录 一、栈的概念及结构 二、栈的头文件及基本框架 三、接口实现 1、对栈的初始化  2、栈的销毁 3、入栈操作 4、出栈操作  5、判断栈是否为空 6、返回栈顶元素 7、遍历栈 四、有效的括号 - 力扣(LeetCode) 题目描述:  思路: 代码: 栈:一种特殊的线性表,其只允许

    2024年02月13日
    浏览(12)
  • 数据结构例题代码及其讲解-链表

    单链表的结构体定义及其初始化。 ①强调结点 LNode *p; ②强调链表 LinkList p; 01 遍历打印 02 按位查找(有一个带头结点的单链表 L,请设计一个算法查找其第 i 个结点位置,若存在则返回指向该结点的指针,若不存在则返回 NULL。) 03 按值查找(有一个带头结点的单链表 L,请

    2024年02月10日
    浏览(18)
  • 数据结构和算法的部分例题(力扣)

    1.1 合并一个数组的两个有序区间 2.1 反转单向链表 (方法1)构建一个新的链表,从就链表依次拿到每个节点,创建新的节点添加至新链表头部,完成后的新链表就是倒序的,简单,但是需要创建新的对象 (方法2)与方法1类似,构建新的链表,从头部移除节点,添加至新链

    2024年01月18日
    浏览(16)
  • 数据结构例题代码及其讲解-顺序表

    静态分配内存及初始化 动态分配内存及初始化 01 对顺序表L进行遍历并输出每个数据元素的数据值 02 假设有一个顺序表L,其存储的所有数据元素均为不重复的正数,查找 L 中值为 e 的数据元素,若找到则返回其下标,若找不到则返回-1。 03 假设有一个顺序表 L,其存储的所有

    2024年02月10日
    浏览(14)
  • 【数据结构与算法】前缀和+哈希表算法

    关于前缀和和哈希这两个概念大家都不陌生,在之前的文章中也有过介绍:前缀和与差分算法详解 而哈希表最经典的一题莫过于 两数之和 题目链接 题目描述: 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它

    2024年02月01日
    浏览(44)
  • 前缀和系列例题详解

    题目 输入一个长度为 n 的整数序列。 接下来再输入 m 个询问,每个询问输入一对 l,r。 对于每个询问,输出原序列中从第 l 个数到第 r 个数的和。 输入格式 第一行包含两个整数 n 和 m。 第二行包含 n 个整数,表示整数数列。 接下来 m 行,每行包含两个整数 l 和

    2023年04月08日
    浏览(11)
  • 数据结构例题代码及其讲解-递归与树

    ​ 树的很多题目中都包含递归的思想 递归 递归包括 递归边界 以及 递归式 即:往下递,往上归 递归写法的特点: 写起来代码较短,但是时间复杂度较高 01 利用递归求解 n 的阶乘。 02 斐波那契数列是满足 F(0)=1,F(1)=1,F(n)=F(n-1)+F(n-2)(n≥2)的数列,数列的前几项为 1,1,2,

    2024年02月09日
    浏览(13)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包