주어진 작업을 수행한 후 가능한 최대 배열 합계

이 질문에서는 배열 요소에 대해 주어진 연산을 수행하고 최종 최대 합계를 구합니다.

여기서 각 작업에서 배열에서 최대 X[p] 요소를 선택하고 이를 Y[p] 요소로 대체하여 합계를 최대화할 수 있습니다.

간단한 방법으로 Y[p] 요소보다 작은 X[p] 배열 요소를 찾아 Y[p]로 대체합니다.

효율적인 접근 방식에서는 우선순위 대기열을 사용하여 최대 합계를 얻습니다.

문제 설명− N개의 숫자를 포함하는 nums[] 배열이 제공됩니다. 동시에 M개의 정수를 포함하는 X[] 및 Y[] 배열이 제공됩니다. nums[] 배열에 대해 다음 작업을 수행해야 합니다.

• 각 X[] 및 Y[] 요소에 대해 M 연산을 수행해야 합니다. 각 작업에서 nums[] 배열에서 가장 큰 X[p] 요소를 선택하고 이를 Y[p]로 바꿔야 합니다.

주어진 작업은 M 연산을 수행한 후 nums[] 배열 요소의 최대 합을 찾는 것입니다.

예제 예

들어가세요

으아악

출력

으아악

설명 − 각 작업을 하나씩 수행해 보겠습니다.

• 첫 번째 작업에서는 7개의 요소를 500개로 대체합니다. 따라서 배열은 {10, 8, 500, 60, 20, 18, 30, 60}이 됩니다.

• 두 번째 작업에서는 최대 2개의 요소를 10으로 대체할 수 있지만 10보다 작은 요소는 1개만 있습니다. 따라서 8을 10으로 바꾸면 배열은 {10, 10, 500, 60, 20, 18, 30, 60}이 됩니다.

• 세 번째 연산에서는 최대 5개의 요소를 2개로 대체할 수 있지만 배열에 2보다 작은 요소는 없습니다. 따라서 우리는 어떤 요소도 교체하지 않을 것입니다.

들어가세요

으아악

출력

으아악

설명 − y[] 배열의 모든 요소는 원래 배열의 요소보다 작습니다. 따라서 최대 합계를 얻기 위해 주어진 배열의 요소를 바꿀 필요가 없습니다.

들어가세요

으아악

출력

으아악

설명 − 여기서는 각 작업에서 최대 x[p]개의 요소를 교체할 수 있습니다. 마지막 작업에서는 배열의 각 요소를 100으로 대체하여 최대 합계가 100이 되도록 할 수 있습니다.

방법 1

이 방법에서는 x[] 및 y[] 배열을 반복합니다. 각 반복에서 y[p] 요소보다 작은 최대 x[p] 배열 요소를 가져오도록 배열을 정렬하고 이를 y[p]로 바꿉니다.

알고리즘

1단계 − 배열 요소의 최대 합계를 저장하는 데 사용되는 'maxSum'을 0으로 초기화합니다.

2단계 − x[] 및 y[] 배열 요소 탐색을 시작합니다.

3단계 − x[p] 값을 임시 변수에 저장하고 nums[] 배열을 정렬합니다.

4단계− 루프 내에서 정렬된 배열 탐색을 시작합니다.

5단계 − 온도가 0보다 크고 nums[q]가 y[p]보다 작은 경우 nums[q]를 y[p]로 업데이트하고 임시 값을 1씩 감소시킵니다.

6단계− 루프 외부에서 업데이트된 배열 순회를 시작하고 모든 배열 요소의 합계를 꺼내서 maxSum 변수에 저장합니다.

7단계 − 함수 끝에서 maxSum을 반환합니다.

예

으아악

출력

으아악

시간 복잡성− O(M*NlogN), 여기서 O(M)은 모든 쿼리를 순회하는 데 사용되고 O(NlogN)은 배열을 정렬하는 데 사용됩니다.

Space Complexity− 배열 정렬의 경우 공간 복잡도는 O(N)입니다.

방법 2

이 방법에서는 우선순위 큐를 사용하여 배열 요소 쌍과 해당 발생 횟수를 저장합니다.

예를 들어, {nums[p],1} 쌍을 각 배열 요소의 우선순위 대기열에 푸시합니다. 동시에 {y[p], x[p]} 쌍을 우선순위 큐에 푸시합니다. 우선순위 대기열에서는 첫 번째 요소를 기준으로 쌍이 정렬됩니다. 따라서 대기열에서 상위 N개의 요소를 가져올 수 있습니다. 여기서 {y[p],x[p]} 쌍의 경우 y[p] 요소를 x[p]번 제거할 수 있으며 합을 최대화하려면 총 N개의 요소를 제거해야 합니다.

알고리즘

1단계 − 요소 쌍과 발생 횟수를 저장하기 위해 'maxSum'을 0과 우선순위 큐로 초기화합니다.

2단계− 모든 배열 요소에 대해 {nums[p], 1} 쌍을 대기열에 삽입합니다.

3단계 − 그런 다음 {y[p], x[p]} 쌍을 우선순위 큐에 삽입합니다.

4단계− n이 0보다 커질 때까지 반복합니다.

4.1단계 − 우선순위 대기열에서 첫 번째 요소를 제거합니다.

4.2단계 − 합계에 first_ele * max(n, second_ele)를 추가합니다. 여기서는 max(n, second_ele)를 사용하여 마지막 경우를 처리합니다.

4.3단계 − n에서 second_ele를 뺍니다.

5단계− maxSum을 반환합니다.

예

으아악

출력

으아악

시간 복잡도 - O(N*logN + m*logm), 여기서 O(N)과 O(m)은 주어진 배열을 순회하는 데 사용되고 O(logN)은 대기열에 요소를 삽입하고 삭제하는 데 사용됩니다.

공간 복잡도 - 대기열에 쌍을 저장하기 위한 O(N+M)입니다.

첫 번째 방법에서는 가장 작은 x[p] 요소를 찾기 위해 각 반복에서 배열을 정렬해야 합니다. 힙 데이터 구조를 사용하므로 요소가 삽입되거나 제거될 때 자동으로 요소를 정렬하려면 우선순위 큐를 사용하세요. 따라서 코드 성능이 향상됩니다.

위 내용은 주어진 작업을 수행한 후 가능한 최대 배열 합계의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!