Mã C ++ để đếm các thao tác sao chép mà không vượt quá k

Giả sử chúng ta có một mảng A với n phần tử và một số k khác. Có n đống kẹo cao su. Cọc thứ i có A [i] số kẹo. Ta có thể thực hiện phép toán trên hai chỉ số i và j (i! =J), sau đó thêm A [i] số kẹo khác vào A [i] (A [i] sẽ không bị giảm). Chúng tôi có thể thực hiện thao tác này bất kỳ số lần nào, nhưng rất tiếc nếu một số đống chứa nhiều hơn k kẹo thì chúng tôi không thể thực hiện thao tác này nữa. Chúng tôi phải tìm số lần tối đa chúng tôi có thể thực hiện thao tác này.

Vì vậy, nếu đầu vào giống như A =[1, 2, 3]; k =5, thì đầu ra sẽ là 5, vì chúng ta có thể lấy i =0 và đối với j =1 chúng ta có thể thực hiện ba lần và với j =2 chúng ta có thể thực hiện hai lần. Như vậy tổng cộng là 5 lần.

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

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

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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;
}

Đầu vào

{ 1, 2, 3 }, 5

Đầu ra

5