网易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)