网易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)
OPPO公司福利 1114人发布
