n, index 및 maxSum의 세 가지 값이 있다고 가정합니다. nums라는 배열을 고려하여 nums[index]를 찾아야 하고 nums는 다음 조건을 충족합니다. -
-
숫자의 크기는 n
입니다. -
n의 모든 요소는 양수입니다.
-
|숫자[i] - 숫자[i+1]| <=모든 i에 대해 1, 0 <=i
-
nums의 모든 요소의 합은 maxSum을 초과하지 않습니다.
-
nums[index]가 최대화됩니다.
따라서 입력이 n =6, index =3, maxSum =8과 같으면 출력은 2가 됩니다. 왜냐하면 [1,2,2,2,1,1]과 같은 배열을 얻을 수 있기 때문입니다. 조건이며 여기에서는 nums[3]이 최대화됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
왼쪽 :=maxSum/n의 몫, 오른쪽 :=maxSum + 1
-
답변 :=0
-
왼쪽 <오른쪽, 하는 동안
-
mid :=왼쪽 + (오른쪽-왼쪽)/2의 몫
-
ind_l :=(mid-1 + 최대 1 및 (mid-index)) * (인덱스 최소 및 (mid-1) /2 + |최소 0, mid-index-1|
의 몫 -
ind_r =(중간 + 최대 1 및 (mid-(n-index-1))) * ((n-index)와 mid의 최소)/2 + |최소 0 및 (mid-(n-index)의 몫 -1)-1)|
-
ind_l + ind_r <=maxSum이면
-
as :=중간
-
왼쪽 :=중간+1
-
-
그렇지 않으면
-
오른쪽 :=중간
-
-
-
반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(n, index, maxSum):
left, right = maxSum//n, maxSum+1
ans = 0
while(left<right):
mid = left + (right-left)//2
ind_l = (mid-1+max(1,mid-index))*min(index,mid-1)//2 + abs(min(0,mid-index-1))
ind_r = (mid+max(1,mid-(n-index-1)))*min(n-index, mid)//2+ abs(min(0,mid-(n-index-1)-1))
if ind_l + ind_r <=maxSum:
ans = mid
left = mid+1
else:
right = mid
return ans
n = 6
index = 3
maxSum = 8
print(solve(n, index, maxSum)) 입력
6, 3, 8
출력
2