当前位置: 首页 > 面试经验 >

网易923笔试-算法类

优质
小牛编辑
100浏览
2023-09-23

网易923笔试-算法类

43.3 100 0 0

咋这么难呢

贴一下第二题代码

题目:小红有个数组,数组相邻长度差值最多为1,并且元素都是正整数。现在小红知道数组长度为n,数组和为m,小红想知道所有符合条件数组中,p位置最大值是多少(起始位置为1)
输入三个整数n,m,p
1<=p<=n<=m<=10**9
思路:二分查找check判断,难点在于怎么快速算出整个数组的最小值,贪心思想,p位置为mid,然后逐渐减一,需要判断两个边界条件,如果减到最小值了还没到边界,就要补1.
n,m,p = map(int,input().split())

def check(mid):
    count = 0
    if p + mid - 1  > n:
        count += (2 * mid - n + p ) * (n - p + 1) / 2
    else:
        count += (mid + 1) * mid / 2 + (n - p - mid + 1)
    if p - mid + 1 <= 0:
        count += (mid-1 + mid - p + 1) * (p - 1) / 2
    else:
        count += mid * (mid - 1) / 2 + (p - mid)
    return count<=m


left,right = 1, m - n + 1
while left < right:
    mid = left + (right - left + 1)//2
    if check(mid):
        left = mid
    else:
        right = mid - 1
print(left)

 类似资料: