주어진 크기의 배열 N 임무는 모든 요소의 가치를 동일하게 만드는 것입니다. 최소 비용 . x에서 y로 값을 변경하는 데 드는 비용은 다음과 같습니다. 절대(x - y).
예:
입력: 도착[] = [1 100 101]
산출 : 100
설명: 최소 비용으로 모든 값을 100으로 변경할 수 있습니다.
|1 - 100| + |100 - 100| + |101 - 100| = 100입력 : arr[] = [4 6]
산출 : 2
설명: 최소 비용으로 모든 값을 5로 변경할 수 있습니다.
|4 - 5| + |5 - 6| = 2입력: 도착[] = [5 5 5 5]
산출:
설명: 모든 값은 이미 동일합니다.
[순진한 접근 방식] 2개의 중첩 루프 사용 - O(n^2) 시간 및 O(1) 공간
C++우리의 대답은 항상 배열 값 중 하나일 수 있다는 점에 유의하세요. 위의 두 번째 예에서도 동일한 비용으로 둘 다 4로 만들거나 둘 다 6으로 만들 수 있습니다.
아이디어는 배열의 각 값을 잠재적인 목표 값으로 간주한 다음 다른 모든 요소를 해당 목표 값으로 변환하는 데 드는 총 비용을 계산하는 것입니다. 가능한 모든 목표 값을 확인하여 전체 전환 비용이 최소가 되는 목표 값을 찾을 수 있습니다.
// C++ program to Make all array // elements equal with minimum cost #include
// Java program to Make all array // elements equal with minimum cost import java.util.*; class GfG { // Function which finds the minimum // cost to make array elements equal static int minCost(int[] arr) { int n = arr.length; int ans = Integer.MAX_VALUE; // Try each element as the target value for (int i = 0; i < n; i++) { int currentCost = 0; // Calculate cost of making all // elements equal to arr[i] for (int j = 0; j < n; j++) { currentCost += Math.abs(arr[j] - arr[i]); } // Update minimum cost if current cost is lower ans = Math.min(ans currentCost); } return ans; } public static void main(String[] args) { int[] arr = {1 100 101}; System.out.println(minCost(arr)); } }
# Python program to Make all array # elements equal with minimum cost # Function which finds the minimum # cost to make array elements equal def minCost(arr): n = len(arr) ans = float('inf') # Try each element as the target value for i in range(n): currentCost = 0 # Calculate cost of making all # elements equal to arr[i] for j in range(n): currentCost += abs(arr[j] - arr[i]) # Update minimum cost if current cost is lower ans = min(ans currentCost) return ans if __name__ == '__main__': arr = [1 100 101] print(minCost(arr))
// C# program to Make all array // elements equal with minimum cost using System; class GfG { // Function which finds the minimum // cost to make array elements equal static int minCost(int[] arr) { int n = arr.Length; int ans = int.MaxValue; // Try each element as the target value for (int i = 0; i < n; i++) { int currentCost = 0; // Calculate cost of making all // elements equal to arr[i] for (int j = 0; j < n; j++) { currentCost += Math.Abs(arr[j] - arr[i]); } // Update minimum cost if current cost is lower ans = Math.Min(ans currentCost); } return ans; } static void Main() { int[] arr = {1 100 101}; Console.WriteLine(minCost(arr)); } }
// JavaScript program to Make all array // elements equal with minimum cost // Function which finds the minimum // cost to make array elements equal function minCost(arr) { let n = arr.length; let ans = Number.MAX_SAFE_INTEGER; // Try each element as the target value for (let i = 0; i < n; i++) { let currentCost = 0; // Calculate cost of making all // elements equal to arr[i] for (let j = 0; j < n; j++) { currentCost += Math.abs(arr[j] - arr[i]); } // Update minimum cost if current cost is lower ans = Math.min(ans currentCost); } return ans; } let arr = [1 100 101]; console.log(minCost(arr));
산출
100
[예상 접근 방식 - 1] 이진 검색을 활용 - O(n Log (Range)) 시간과 O(1) 공간
아이디어는 이진 검색을 활용하여 모든 배열 요소를 변환해야 하는 최적의 값을 효율적으로 찾는 것입니다. 총 비용 함수는 가능한 값의 범위에 걸쳐 볼록한 곡선(먼저 감소한 다음 증가함)을 형성하므로 이진 검색을 사용하여 중간 지점의 비용과 중간 지점의 비용에서 1을 뺀 값을 비교하여 이 곡선의 최소점을 찾을 수 있으며 이는 어느 방향으로 더 검색해야 하는지 알려줍니다.
단계별 접근 방식:
- 배열에서 최소값과 최대값을 찾아 검색 범위를 설정합니다.
- 최소값과 최대값 사이의 이진 검색을 사용하여 최적의 목표값을 찾습니다.
- 각 평가판 값에 대해 모든 배열 요소를 해당 값으로 변환하는 데 드는 총 비용을 계산합니다.
- 현재 중간점의 비용과 중간점의 비용에서 1을 뺀 값을 비교하여 검색 방향을 결정합니다.
- 최소 비용 구성을 찾을 때까지 검색 범위를 계속 좁힙니다.
// C++ program to Make all array // elements equal with minimum cost #include
// Java program to Make all array // elements equal with minimum cost import java.util.*; class GfG { // Function to find the cost of changing // array values to mid. static int findCost(int[] arr int mid) { int n = arr.length; int ans = 0; for (int i = 0; i < n; i++) { ans += Math.abs(arr[i] - mid); } return ans; } // Function which finds the minimum cost // to make array elements equal. static int minCost(int[] arr) { int n = arr.length; int mini = Integer.MAX_VALUE maxi = Integer.MIN_VALUE; // Find the minimum and maximum value. for (int i = 0; i < n; i++) { mini = Math.min(mini arr[i]); maxi = Math.max(maxi arr[i]); } int s = mini e = maxi; int ans = Integer.MAX_VALUE; while (s <= e) { int mid = s + (e - s) / 2; int cost1 = findCost(arr mid); int cost2 = findCost(arr mid - 1); if (cost1 < cost2) { ans = cost1; s = mid + 1; } else { e = mid - 1; } } return ans; } public static void main(String[] args) { int[] arr = {1 100 101}; System.out.println(minCost(arr)); } }
# Python program to Make all array # elements equal with minimum cost # Function to find the cost of changing # array values to mid. def findCost(arr mid): n = len(arr) ans = 0 for i in range(n): ans += abs(arr[i] - mid) return ans # Function which finds the minimum cost # to make array elements equal. def minCost(arr): n = len(arr) mini = float('inf') maxi = float('-inf') # Find the minimum and maximum value. for i in range(n): mini = min(mini arr[i]) maxi = max(maxi arr[i]) s = mini e = maxi ans = float('inf') while s <= e: mid = s + (e - s) // 2 cost1 = findCost(arr mid) cost2 = findCost(arr mid - 1) if cost1 < cost2: ans = cost1 s = mid + 1 else: e = mid - 1 return ans if __name__ == '__main__': arr = [1 100 101] print(minCost(arr))
// C# program to Make all array // elements equal with minimum cost using System; class GfG { // Function to find the cost of changing // array values to mid. static int findCost(int[] arr int mid) { int n = arr.Length; int ans = 0; for (int i = 0; i < n; i++) { ans += Math.Abs(arr[i] - mid); } return ans; } // Function which finds the minimum cost // to make array elements equal. static int minCost(int[] arr) { int n = arr.Length; int mini = int.MaxValue maxi = int.MinValue; // Find the minimum and maximum value. for (int i = 0; i < n; i++) { mini = Math.Min(mini arr[i]); maxi = Math.Max(maxi arr[i]); } int s = mini e = maxi; int ans = int.MaxValue; while (s <= e) { int mid = s + (e - s) / 2; int cost1 = findCost(arr mid); int cost2 = findCost(arr mid - 1); if (cost1 < cost2) { ans = cost1; s = mid + 1; } else { e = mid - 1; } } return ans; } static void Main() { int[] arr = {1 100 101}; Console.WriteLine(minCost(arr)); } }
// JavaScript program to Make all array // elements equal with minimum cost // Function to find the cost of changing // array values to mid. function findCost(arr mid) { let n = arr.length; let ans = 0; for (let i = 0; i < n; i++) { ans += Math.abs(arr[i] - mid); } return ans; } // Function which finds the minimum cost // to make array elements equal. function minCost(arr) { let n = arr.length; let mini = Number.MAX_SAFE_INTEGER maxi = Number.MIN_SAFE_INTEGER; // Find the minimum and maximum value. for (let i = 0; i < n; i++) { mini = Math.min(mini arr[i]); maxi = Math.max(maxi arr[i]); } let s = mini e = maxi; let ans = Number.MAX_SAFE_INTEGER; while (s <= e) { let mid = Math.floor(s + (e - s) / 2); let cost1 = findCost(arr mid); let cost2 = findCost(arr mid - 1); if (cost1 < cost2) { ans = cost1; s = mid + 1; } else { e = mid - 1; } } return ans; } let arr = [1 100 101]; console.log(minCost(arr));
산출
100
[예상 접근 방식 - 2] 정렬 활용 - O(n Log n) 시간과 O(1) 공간
아이디어는 기존 배열 요소 중 하나여야 하는 모든 요소를 균등화해야 하는 최적의 값을 찾는 것입니다. 먼저 배열을 정렬한 다음 잠재적인 목표 값으로 각 요소를 반복함으로써 현재 위치의 왼쪽과 오른쪽에 있는 요소의 합을 효율적으로 추적하여 다른 모든 요소를 해당 값으로 변환하는 비용을 계산합니다.
단계별 접근 방식:
- 요소를 오름차순으로 처리하도록 배열을 정렬합니다.
- 각 요소에 대해 잠재적 목표 값으로 두 가지 비용을 계산합니다. 즉, 작은 요소를 위로 가져오고 큰 요소를 아래로 가져옵니다.
- 왼쪽 및 오른쪽 합계를 추적하여 반복당 일정한 시간에 이러한 비용을 효율적으로 계산합니다.
- 더 작은 요소를 가져오는 비용: (현재 가치 × 더 작은 요소 수) - (더 작은 요소의 합계)
- 큰 요소를 줄이는 비용: (큰 요소의 합계) - (현재 가치 × 큰 요소 수)
- 현재 비용과 최소 비용을 비교하세요.
// C++ program to Make all array // elements equal with minimum cost #include
// Java program to Make all array // elements equal with minimum cost import java.util.*; class GfG { // Function which finds the minimum cost // to make array elements equal. static int minCost(int[] arr) { int n = arr.length; // Sort the array Arrays.sort(arr); // Variable to store sum of elements // to the right side. int right = 0; for (int i = 0; i < n; i++) { right += arr[i]; } int ans = Integer.MAX_VALUE; int left = 0; for (int i = 0; i < n; i++) { // Remove the current element from right sum. right -= arr[i]; // Find cost of incrementing left side elements int leftCost = i * arr[i] - left; // Find cost of decrementing right side elements. int rightCost = right - (n - 1 - i) * arr[i]; ans = Math.min(ans leftCost + rightCost); // Add current value to left sum left += arr[i]; } return ans; } public static void main(String[] args) { int[] arr = {1 100 101}; System.out.println(minCost(arr)); } }
# Python program to Make all array # elements equal with minimum cost # Function which finds the minimum cost # to make array elements equal. def minCost(arr): n = len(arr) # Sort the array arr.sort() # Variable to store sum of elements # to the right side. right = sum(arr) ans = float('inf') left = 0 for i in range(n): # Remove the current element from right sum. right -= arr[i] # Find cost of incrementing left side elements leftCost = i * arr[i] - left # Find cost of decrementing right side elements. rightCost = right - (n - 1 - i) * arr[i] ans = min(ans leftCost + rightCost) # Add current value to left sum left += arr[i] return ans if __name__ == '__main__': arr = [1 100 101] print(minCost(arr))
// C# program to Make all array // elements equal with minimum cost using System; class GfG { // Function which finds the minimum cost // to make array elements equal. static int minCost(int[] arr) { int n = arr.Length; // Sort the array Array.Sort(arr); // Variable to store sum of elements // to the right side. int right = 0; for (int i = 0; i < n; i++) { right += arr[i]; } int ans = int.MaxValue; int left = 0; for (int i = 0; i < n; i++) { // Remove the current element from right sum. right -= arr[i]; // Find cost of incrementing left side elements int leftCost = i * arr[i] - left; // Find cost of decrementing right side elements. int rightCost = right - (n - 1 - i) * arr[i]; ans = Math.Min(ans leftCost + rightCost); // Add current value to left sum left += arr[i]; } return ans; } static void Main() { int[] arr = {1 100 101}; Console.WriteLine(minCost(arr)); } }
// JavaScript program to Make all array // elements equal with minimum cost // Function which finds the minimum cost // to make array elements equal. function minCost(arr) { let n = arr.length; // Sort the array arr.sort((a b) => a - b); // Variable to store sum of elements // to the right side. let right = 0; for (let i = 0; i < n; i++) { right += arr[i]; } let ans = Number.MAX_SAFE_INTEGER; let left = 0; for (let i = 0; i < n; i++) { // Remove the current element from right sum. right -= arr[i]; // Find cost of incrementing left side elements let leftCost = i * arr[i] - left; // Find cost of decrementing right side elements. let rightCost = right - (n - 1 - i) * arr[i]; ans = Math.min(ans leftCost + rightCost); // Add current value to left sum left += arr[i]; } return ans; } let arr = [1 100 101]; console.log(minCost(arr));
산출
100퀴즈 만들기