k를 초과하지 않고 복사 작업을 계산하는 C++ 코드

n개의 요소와 또 다른 숫자 k가 있는 배열 A가 있다고 가정합니다. n개의 사탕 더미가 있습니다. i번째 더미에는 A[i]개의 사탕이 있습니다. 두 개의 인덱스 i와 j(i !=j)에 대해 연산을 수행한 다음 A[i]에 또 다른 A[i] 수의 사탕을 추가할 수 있습니다(A[i]는 감소되지 않음). 우리는 이 작업을 여러 번 수행할 수 있지만 불행히도 일부 더미에 k개 이상의 사탕이 엄격하게 포함되어 있으면 더 이상 작업을 수행할 수 없습니다. 이 작업을 수행할 수 있는 최대 횟수를 찾아야 합니다.

따라서 입력이 A =[1, 2, 3]과 같으면; k =5이면 출력은 5가 됩니다. 왜냐하면 i =0을 취할 수 있고 j =1에 대해 세 번 수행할 수 있고 j =2에 대해 두 번 수행할 수 있기 때문입니다. 총 5번입니다.

단계

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

ans := 0
n := size of A
sort the array A
for initialize i := 1, when i < n, update (increase i by 1), do:
   ans := ans + (k - A[i])
return ans

예

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A, int k){
   int ans = 0;
   int n = A.size();
   sort(A.begin(), A.end());
   for (int i = 1; i < n; i++){
      ans += (k - A[i]) / A[0];
   }
   return ans;
}
int main(){
   vector<int> A = { 1, 2, 3 };
   int k = 5;
   cout << solve(A, k) << endl;
}

입력

{ 1, 2, 3 }, 5

출력

5