3
우리는 n 개의 양의 정수 배열을 가지고 있습니다. 허용되는 조치는 요소를 1 씩 증가시키고 이웃 중 하나를 1 씩 감소시키는 것입니다.배열의 균형을 잡기위한 최소 이동
최종 배열의 최소 및 최대 값은 최대 1과 달라야합니다.
예를 들어 초기 배열이 {5, 6, 4, 1, 10}이면 대답은 5가되고 최종 배열은 {5, 5, 5, 5, 6}이 될 수 있습니다.
A
답변
2
이 문제에 대해 Divide and Conquer를 사용할 수 있습니다.
모든 요소의 최종 값은 배열의 모든 요소의 평균이어야합니다. 평균이 정수가 아니면 MAX와 MIN의 두 가지 값을 정의 할 수 있습니다. MAX는 평균의 한도이며 MIN은 평균의 바닥입니다. (http://en.wikipedia.org/wiki/Floor_and_ceiling_functions)
이제 어레이를 2 등분하십시오. [0 - n/2] 및 [n/2 +1 - n-1]로 구성된다. n이 홀수 인 경우 첫 번째 절반은 더 작을 것이지만 이것은 중요하지 않습니다.
각 반마다 모든 요소의 평균을 계산하십시오. 이 평균은 MAX 또는 MIN과 같습니다. 그렇지 않은 경우,이 평균은 필요에 따라 증가되거나 감소되어야합니다.
이제 주목할 점은 하위 배열의 평균은 해당 하위 배열 내에서만 요소가 포함 된 연산으로 수정할 수 없다는 것입니다. 그래서 어떤 변경이라도 n/2 th와 n/2 + 1 th 요소 사이의 연산이 필요합니다.
또 하나의 주목할 점은 하나의 서브 어레이가 평균보다 적은 평균값을 갖는다면, 다른 서브 어레이는 평균 이상을 요구한다는 것입니다.
2 개의 중간 요소 사이에서 적절한 작업을 쉽게 수행 할 수 있습니다.
이제 각 하위 배열을 두 개로 나누고 프로세스를 반복하십시오.
[참고 : 반복 간격 트리를 사용하여 두 업데이트뿐만 아니라 가산 연산에 대한 로그 시간에서 carrried 수있는 서브 어레이의 평균값을 계산하는 데 필요한 동작들을 합산 http://en.wikipedia.org/wiki/Interval_tree]
+0
당신의 솔루션에는 탐욕스러운 사실이 있습니다. 가능한 한 적은 두 개의 중간 요소 사이를 1로 이동하십시오. (이유는 무엇입니까?) –
+0
위에서 말한 것처럼 모든 하위 배열의 평균을 높이거나 낮추는 유일한 방법은 값을 /에서 다른 하위 배열로/그 하위 배열로. 왜 이것이 필요합니까? 최종 배열에서 해당 배열 내의 모든 하위 배열은 MIN과 MAX 사이의 평균을 가져야합니다. 게다가, 나는 O (n) 욕심 많은 해결책이 가능하다고 생각하지 않는다. (아마도 합계 연산이 어떻게 구현되는지에 따라 아마도 O (n log n)이 더 많을 것이다.) – arya
+0
당신은 당신의 서브 - 배열을 사용하여 평균을 [MIN, MAX]로 가져오고 더 이상 움직이지 않습니다. 나중에 1 초 이상 움직이면 도움이 될까요? 알고리즘이 정확하다면, 작업 할 때마다 1 길이의 서브 배열을 제거 할 수 있습니다 : 매번 첫 번째 요소의 값까지 이동하고 나머지 요소의 평균은 [MIN, MAX]가됩니다. O (n)에서 작동합니다. 알고리즘에서 나누고 정복하는 데 도움이되는 것은 무엇입니까? –
I가 없어 그것을위한 다항식 알고리즘을 가지고 있습니다. –
SO가 알고리즘을 제공하지 않습니다. 문제에 대해 생각하고 직관을 알아 냈습니까? – simchona
만약 우리가 목표 배열을 알고 있다면 그것은 O (n)에서 풀릴 것이다; 그냥 배열을 청소하고 탐욕스럽게 움직이십시오. 아마 배열의 접미사와 같은 동적 인 솔루션이 k 개의 최대 값을 가지고 있다고 생각했을 지 모르지만 전에는 좀 탐욕스러운 움직임이 필요합니다. –