C++ 프로그램: 모든 선물의 수량을 동일하게 만드는 데 필요한 작업 수 계산

각각 크기가 n인 두 개의 배열 A와 B가 있다고 가정합니다. n개의 선물이 있고 우리는 그것을 몇몇 아이들에게 주고 싶습니다. i번째 선물은 A[i] 사탕과 B[i] 오렌지로 구성됩니다. 이동하는 동안 일부 선물을 선택하고 다음 작업 중 하나를 수행할 수 있습니다.

• 이 선물에서 사탕을 꺼냅니다(있는 경우). p>

• 이 선물에서 오렌지를 꺼냅니다(있는 경우).

• 이 선물에서 사탕 하나와 오렌지 선물 하나를 꺼냅니다(있는 경우).

모든 선물은 평등하게 창조되어야 합니다. 이는 일련의 이동 후에 다음 두 가지가 수행됨을 의미합니다. 조건은 충족되어야 합니다: A[0] = A[1] = ... = A[n-1] 및 B[0] = B[1] = ... = B[n-1]. 우리는해야 주어진 모든 선물을 동일하게 만드는 데 필요한 최소 단계 수를 찾으십시오.

문제 카테고리

위의 문제는 탐욕스러운 문제 해결 기법을 적용하면 해결될 수 있습니다. 그리디 알고리즘 기술은 현재 최고의 솔루션을 제공하는 알고리즘의 한 종류입니다. 가능한 모든 해결 방법을 시도하기보다는 선택하십시오. 그리디 알고리즘 기술도 형 동적 프로그래밍과 마찬가지로 최적화 문제를 해결하는 데 사용됩니다. 활동적인 프로그래밍할 때 가능한 모든 하위 문제를 탐색하고 최적의 문제를 찾아야 합니다. 하지만 더 많은 시간과 공간이 필요하다는 단점이 있습니다. 그러므로 다양한 곳에서 시나리오 탐욕 기법은 문제에 대한 최선의 해결책을 찾는 데 사용됩니다. 사실이지만 모든 경우에 최상의 솔루션을 제공하지는 않습니다. 신중하게 설계하면 다음보다 빠르게 솔루션을 생성할 수 있습니다. 동적 프로그래밍 문제. Greedy 기술은 로컬 최적의 솔루션을 제공합니다. 최적화. 이 기술의 예로는 Kruskal과 Prim의 최소가 있습니다. 스패닝 트리(MST) 알고리즘, 허프만 트리 코딩, Dijkstra의 단일 소스 최단 경로 질문 등등

https://www.tutorialspoint.com/data_structurals_algorithms/greedy_algorithms.htm

https://www.tutorialspoint.com/data_structurals_algorithms/dynamic_programming.htm p>

그래서 우리 문제에 대한 입력이 이렇다면 A = [3, 5, 6]; B = [3, 2, 3]이면 출력은 6입니다. 원래 B에서 가져왔으므로 이제 B[0]은 [2, 2, 3]이 되고 A[1]에서 가져오므로 A = [3, 4, 6], 그리고 다시 A[1]에서, 따라서 A = [3, 3, 6]에서, 그리고 A[2]와 B[2]에서, 따라서 그들은 [3, 3, 5] 및 [2, 2, 2]로, A[2]에서 A = [3, 3, 4]로, 다시 A[2]에서 [3, 3, 3]이라고 합시다. 이제 A는 같은 수의 사탕을 가지고 있고 B는 같은 수의 오렌지를 가지고 있습니다.

단계

이 문제를 해결하기 위해 다음 단계를 따릅니다. -

minA := inf
minB := inf
kq := 0
n := size of A
for initialize i := 0, when i < n, update (increase i by 1), do:
   minA := minimum of minA and A[i]
for initialize i := 0, when i < n, update (increase i by 1), do:
   minB := minimum of minB and B[i]
for initialize i := 0, when i < n, update (increase i by 1), do:
   kq := kq + maximum of (A[i] - minA) and (B[i] - minB)
return kq

Example

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. -

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A, vector<int> B){
   int minA = 999, minB = 999, kq = 0;
   int n = A.size();
   for (int i = 0; i < n; i++)
      minA = min(minA, A[i]);
   for (int i = 0; i < n; i++)
      minB = min(minB, B[i]);
   for (int i = 0; i < n; i++)
      kq += max(A[i] - minA, B[i] - minB);
   return kq;
}
int main(){
   vector<int> A = { 3, 5, 6 };
   vector<int> B = { 3, 2, 3 };
   cout << solve(A, B) << endl;
}

Input

{ 3, 5, 6 }, { 3, 2, 3 }

Output

6

위 내용은 C++ 프로그램: 모든 선물의 수량을 동일하게 만드는 데 필요한 작업 수 계산의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!