Viết chương trình bằng C++

Công ty XYZ cần phải làm ra M loại sản phẩm khác nhau. Loại sản phẩm thứ i có số lượng là ai chiếc. Công ty có N con robot có thể tự động sản xuất ra sản phẩm tuy nhiên mỗi robot chỉ có thể làm được một loại sản phẩm với số lượng không giới hạn. Có thể không cần phải sử dụng hết cả N robot để tạo sản phẩm. Độ hao mòn của robot bằng số lượng sản phẩm làm ra nhiều nhất của một con robot nào đó trong N con.

Ví dụ: Có 5 robot làm ra 2 loại sản phẩm như sau: robot 1 làm 4 sản phẩm loại 1, robot 2 làm 2 sản phẩm loại 1, robot 3 làm 1 sản phẩm loại 1, robot 4 làm 3 sản phẩm loại 2, robot 5 làm 1 sản phẩm loại 2. Độ hao mòn robot = max(4, 2, 1, 3, 1) = 4.

Yêu cầu: Cho N robot và cần làm M loại sản phẩm khác nhau với số lượng lần lượt là $a_{1}$, $a_{2}$,...$a_{M}$ . Tính độ hao mòn nhỏ nhất của robot.

Input

- Dòng đầu tiên chứa 2 số nguyên N (1≤N≤$10^{9}$ ) và M (1≤M≤$10^{5}$ ).

- Dòng thứ hai ghi M số nguyên dương $a_{1}$, $a_{2}$,...$a_{M}$ (1≤ $a_{i}$ ≤ $10^{9}$ ,1≤ i ≤M). Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Output

Ghi một số nguyên T là độ hao mòn nhỏ nhất của robot tìm được.

Sample Input 5 2 7 4

Sample Output 3

Giải thích:

Sử dụng cả 5 robot. Khi đó độ hao mòn nhỏ nhất của robot là 3.

Sản phẩm $a_{1}$: Sử dụng ba robot trong đó: Hai robot mỗi con làm ra 3 sản phẩm, một robot làm 1 sản phẩm.

Sản phẩm $a_{2}$: Sử dụng hai robot trong đó: Một robot làm ra 3 sản phẩm, một robot làm 1 sản phẩm.

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


#define pii pair<int, int>
const int ar = 1e9 + 7;
const int nmax = 1e6 + 1;
long long a[nmax], n, m, ans = 0;
bool check (long long k) {
    long long d = 0;
    for (long long i = 1; i <= m; ++i) {
        if (a[i] % k == 0) {
            d += a[i] / k;
        }
        else {
            d += a[i] / k + 1;
        }
    }
    return d <= n;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for (long long i = 1; i <= m; ++i) cin >> a[i];
    long long l = 1, r = *max_element(a + 1, a + 1 + m);
    while (l <= r) {
        long long mid = (l + r) / 2;
        if (check(mid)) {
            ans = mid;
            r = mid - 1;
        }
        else {
            l = mid + 1;
        }
    }
    cout << ans;
    return 0;
}

#include <iostream>
using namespace std;
bool cpc(int a[], int m, int n, long long mi)
{
    long long rc = 0;
    for (int i = 0; i < m; i++)
    {
        rc += (a[i] + mi - 1) / mi;
        if (rc > n) return false;
    }
    return rc <= n;
}
int main()
{
    int n, m;
    cin >> n >> m;
    int a[m];
    long long sum = 0;
    for (int i = 0; i < m; i++)
    {
        cin >> a[i];
        sum += a[i];
    }
    long long l = 1, r = sum, kq = r;
    while (l <= r)
    {
        long long mi = l + (r - l) / 2;
        if (cpc(a, m, n, mi))
        {
            kq = mi;
            r = mi - 1;
        }
        else
            l = mi + 1;
    }
    cout << kq << endl;
    return 0;
}

$#khanhtaon$