세 개의 값 n, total 및 k가 있다고 가정합니다. 이제 합이 total과 같고 연속적인 두 요소 간의 절대 차이가 최대 1인 크기 n의 목록을 고려합니다. 이러한 목록의 인덱스 k에서 최대값을 찾아야 합니다.
따라서 입력이 n =5 total =15 k =3과 같으면 출력은 4가 됩니다. 하나의 가능한 목록은 [3,2,3,4,3], 인덱스 3에서 발견되는 최대 요소이기 때문입니다. 4입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- x :=0
- 다음을 반복하다, do
- a :=k + 1
- s :=(x + x - a + 1) * a/2인 경우 바닥
- a :=n - k
- s :=s +(x + x - a + 1) * a/2의 바닥
- s :=s - x
- if s> 총계이면
- 루프에서 나오다
- x :=x + 1
- 반환 x - 1
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(n, total, k): x = 0 while 1: a = k + 1 s = (x + x - a + 1) * a // 2 a = n - k s += (x + x - a + 1) * a // 2 s -= x if s > total: break x += 1 return x - 1 n = 5 total = 15 k = 3 print(solve(n, total, k))
입력
5, 15, 3
출력
4