蓝桥杯刷题015——最少刷题数(二分法+前缀和)

这篇具有很好参考价值的文章主要介绍了蓝桥杯刷题015——最少刷题数(二分法+前缀和)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

问题描述

小蓝老师教的编程课有 N 名学生, 编号依次是 1…N 。第 i 号学生这学期刷题的数量是 Ai​ 

对于每一名学生, 请你计算他至少还要再刷多少道题, 才能使得全班刷题比他多的学生数不超过刷题比他少的学生数。

输入格式

第一行包含一个正整数 N 。

第二行包含 N 个整数:A1​,A2​,A3​,…,AN​.                         

输出格式

输出 N 个整数, 依次表示第 1…N 号学生分别至少还要再刷多少道题。

样例输入

5
12 10 15 20 6

样例输出

0 3 0 0 7

评测用例规模与约定

对于 30% 的数据,1≤N≤1000,0≤Ai​≤1000.

对于 100% 的数据, 1≤N≤100000,0≤Ai​≤100000.

题目大意

给出一个序列表示每个人目前的刷题数,计算每个人最少再刷多少题,可使得刷题数比他多的人数不超过刷题数比他少的人数。

解题关键:

给出一个数字,计算出序列中比它大的数字个数和比它小的数字个数

解题思路一:二分        算法复杂度:

  • 给定一个数字,可以通过二分查找的方式确定它在一个有序序列中所处的下标,根据下标位置,可以确定大于它的数字数和小于它的数字数,从而完成“多刷题人数”和“少刷题人数”的确定,假设用more和fewer来表示。
  • 小的刷题数对应较大的more和较小的fewer,大的刷题数对应较小的more和较大的fewer,因此根据这样的有序性,我们可以对每个同学的刷题数使用二分算法,找出使more<=fewer的最小值。
  • check()函数设置为检查more<=fewer,满足返回True,否则返回False。复杂度为O(logn)

参考代码1:通过70%数据测试 

import bisect
n = int(input())
a = list(map(int, input().split()))
sa = sorted(a)                              #获取一份和a相同的,但经过排序的列表

# #判断刷题数为cur时,刷题数比他多的人数是否不超过比他小的人数
def check(cur, raw):                        
    few = bisect.bisect_left(sa, cur)       #使用二分的方式,通过查找元素位置,计算数目    
    fewer = few if cur == raw else few - 1  #当cur的值相较原本已经增加,这时判断少刷题人数要扣掉自己
    more = len(sa) - bisect.bisect_right(sa, cur)   #计算多刷题的人数
    if more <= fewer:                       #判断情况
        return True
    else:
        return False

max_num = sa[-1]                            #获取所有人中刷题最多的题数,作为二分的右边界
res = []                                    #记录每人为实现目标要多刷的题数
for i in range(n):
    l, r = a[i] - 1, max_num + 1            #l,r是新的刷题数,标定左右边界
    while l + 1 != r:                       #二分算法
        mid = l + r >> 1
        if not check(mid, a[i]):            #刷题数不达标,说明当前题数还较少,压缩左边界
            l = mid
        else:
            r = mid                         #否则压缩右边界
    res.append(r - a[i])                    #最终符合要求的结果在r所指范围中,用r减去a[i]即可得到需要多刷的题数
print(*res)

优化一:对check()优化:前缀和

使用前缀和避免重复计算              算法复杂度:O(nlogn)

示例:5个学生,刷题数分别是12,10,8,15,6

1、建一个列表cnt统计每个刷题数对应的学生数
2、计算该列表的前缀和列表scnt,特别赋值scnt[0]=cnt[0],因为本题Ai是从0开始的,但其实前缀和的0一般不用,是从1开始的。

计算前缀和:  或者    蓝桥杯刷题015——最少刷题数(二分法+前缀和)蓝桥杯刷题015——最少刷题数(二分法+前缀和)

例如:刷题数为10的人,比他多的人more可以用scnt[M] - scnt[cur]=5-3=2,比他少的人fewer可以用前一个前缀和scnt[cur-1] =  scnt[cur] - cnt[cur]=3-1=2,如果是通过再刷题达到的刷题数cur,那么fewer需要再-1,减掉一个再刷题前的自己。(因为需要再刷题说明肯定比之前刷题数多)

参考代码2:通过100%数据测试  

n = int(input())
a = list(map(int, input().split()))
N = 100010                          # 稍微比范围大一点
cnt = [0] * N; scnt = [0] * N       # 最后多的0没有影响
for i in range(n):
    cnt[a[i]] += 1                  # 统计刷题数为ai的人数

scnt[0] = cnt[0]                    #  特别赋值
for i in range(1, N):
    scnt[i] = scnt[i - 1] + cnt[i]  # 刷题数i的前缀和

def check(x, old):
    more = scnt[N - 1] - scnt[x]    # more:所有人数 - 刷题数x的前缀和
    fewer = scnt[x] - cnt[x]        # fewer:刷题数x的前缀和 - 刷题数x的人数
    if x != old:                    # 需要达到刷题数和原来刷题数不一样
        fewer -= 1                  # 减掉一个原来的自己
    if more <= fewer:
        return True
    else:
        return False

res = []                            # 记录每人为实现目标要多刷的题数
for i in range(n):
    l, r = a[i] - 1, 100001
    while l + 1 != r:
        mid = l + r >> 1            # 右移1等价于//2
        if check(mid, a[i]):
            r = mid
        else:
            l = mid
    res.append(r - a[i])            # 需要多刷的题数 = 最少需要达到的刷题数r - 原来刷题数a[i]
print(*res)                         # 加个*,可以打印出列表的每个元素,用空格隔开

优化二:前缀和+一次二分找中间数

        通过前面的做法,我们发现,对于需要多刷题的人,他们最后都会刷到同一个题目数。例如样例中他们最后都会刷到同一个题目数13.
        因此,我们选出一个最小的当前刷题数,用一次二分查找即可确定将要刷到的题数,记为pos
之后遍历a中所有数字,check()不需要再二分查找pos,如果满足check(),就说明新刷题数是0,否则新刷题数是pos - a[i]
算法复杂度:O(n)

参考代码3:通过100%数据测试 

n = int(input())
a = list(map(int, input().split()))
t = min(a)                            # 选出刷题数最少的,后面进行一次二分查找
N = 100010
cnt = [0] * N; scnt = [0] * N
for i in range(n):
    cnt[a[i]] += 1

scnt[0] = cnt[0]
for i in range(1, N):
    scnt[i] = scnt[i - 1] + cnt[i]

def check(x, old):
    more = scnt[N - 1] - scnt[x]
    fewer = scnt[x] - cnt[x]
    if x != old:
        fewer -= 1
    if more <= fewer:
        return True
    else:
        return False

# 没有for循环,只需要做一次二分
l, r = t - 1, 100001
while l + 1 != r:
    mid = l + r >> 1
    if check(mid, t):
        r = mid
    else:
        l = mid
pos = r    # 最少需要达到的刷题数pos
res = []
for i in range(n):               
    if check(a[i], a[i]):        # 已经满足more <= fewer
        res.append(0)            # 不需要刷题
    else:                        # 不满足more <= fewer
        res.append(pos - a[i])   # 需要多刷的题数 = 最少需要达到的刷题数 - 原来刷题数
print(*res)


 文章来源地址https://www.toymoban.com/news/detail-413003.html

到了这里,关于蓝桥杯刷题015——最少刷题数(二分法+前缀和)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 蓝桥杯上岸每日N题 第四期(最少刷题数)!!!

    前缀和: 二分 (1)情况1 (2)情况2 对于每一名学生,请你计算他至少还要再刷多少道题,才能使得全班刷题比他多的学生数不超过刷题比他少的学生数。 全班刷题比他多的学生数不超过刷题比他少的学生数。 换句话说:全班刷题比他少的学生数=(大于等于)全班刷题比他多的学

    2024年02月14日
    浏览(63)
  • 第十三届蓝桥杯 Java B 组省赛 D 题—— 最少刷题数(AC)

    小蓝老师教的编程课有 N N N 名学生, 编号依次是 1 … N 1…N 1 … N 。第 i i i 号学生这学期 刷题的数量是 A i A_{i} A i ​ 。 对于每一名学生, 请你计算他至少还要再刷多少道题, 才能使得全班刷题 比他多的学生数不超过刷题比他少的学生数。 第一行包含一个正整数 N N N 。 第二

    2023年04月09日
    浏览(43)
  • 二分法相关使用

    在线OJ:704. 二分查找 有序数组下的二分思路如下: 由于这里是有序数组, 我们可以可以先得到中点位置, 中点可以把数组分为左右两边; 如果中点位置的值等于目标值, 直接返回中点位置; 如果中点位置的值小于目标值, 则去数组中点左侧按同样的方式查找; 如果中点位置的值大

    2024年02月07日
    浏览(44)
  • 二分法MATLAB代码

    本质是通过不断进行区间压缩来获取函数零点。 二分法的终止条件:区间长度小于等于精度要求 。 流程: 如下图所示:

    2024年02月05日
    浏览(47)
  • 二分法简单题

    2024年01月24日
    浏览(55)
  • 初探二分法

    智能化校园:深入探讨云端管理系统设计与实现(一) 智能化校园:深入探讨云端管理系统设计与实现(二) 题目:给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。 提示: 你可以

    2024年01月25日
    浏览(59)
  • 【算法】—二分法详解

    ①定义: 二分查找算法也称折半搜索算法,对数搜索算法,是一种在 有序数组 中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素

    2024年02月09日
    浏览(52)
  • 【二分查找】一文带你掌握二分法 (附万能模板)

    一、简介 哪怕没有学过编程的同学,也许不知道二分法这个名字,但也一定接触过它的核心思想。不了解的同学也没关系,我用一句话就能概括出它的精髓: 将一个区间一分为二,每次都舍弃其中的一部分。 二分法能够极大地降低我们在解决问题时的时间复杂度。假如你要

    2024年01月19日
    浏览(58)
  • 【剑指Offer】二分法例题

    链表是数据结构中重要的一个章节,他的重要性也不言而喻,在未来不管是笔试还是面试都会遇到这类的题目,所以接下来我就会把一些链表的常考的题目全部整理出来供大家学习指正。 题目链接 描述: 给定一个长度为n的数组nums,请你找到峰值并返回其索引。数组可能包

    2023年04月13日
    浏览(46)
  • 非线性方程二分法

    优点:算法直观、简单、总能保证收敛;局限:收敛速度慢、一般不单独用它求根,仅为了获取根的粗略近似 设 f ( x ) f(x) f ( x ) 在 [ a , b ] [a,b] [ a , b ] 上连续、严格单调、满足条件 f ( a ) f ( b ) 0 f(a)f(b)0 f ( a ) f ( b ) 0 则在区间 [ a , b ] [a,b] [ a , b ] 内必有一根 x ∗ x^* x ∗ 。通

    2024年02月04日
    浏览(48)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包