Đếm số phép sao chép mảng không vượt quá k bằng C++

Mô tả bài toán

Mảng A n phần tử, giới hạn k. Phép toán: chọn i≠j, cộng A[i] vào A[j] (A[i] không đổi). Dừng khi có phần tử > k. Tối đa số phép.

Ví dụ

A=[1,2,3], k=5 → Sắp xếp: [1,2,3]. Dùng phần tử nhỏ nhất (1) cộng vào các phần tử khác: (5-2)/1=3, (5-3)/1=2 → tổng 5.

Thuật toán

Sắp xếp A. Phần tử nhỏ nhất A[0]. Với mỗi i>0, số lần cộng A[0] vào A[i] mà không vượt k là (k - A[i]) / A[0]. Tổng tất cả.

Code C++

#include <bits/stdc++.h>
using namespace std;

int solve(vector A, int k) {
    sort(A.begin(), A.end());
    int ans = 0;
    for (int i = 1; i < (int)A.size(); i++)
        ans += (k - A[i]) / A[0];
    return ans;
}

int main() {
    vector A = {1,2,3};
    int k = 5;
    cout << solve(A, k) << endl;
    return 0;
}

Đầu vào / Đầu ra

Input: {1,2,3}, 5

Output: 5