Tặng hoa
Xem PDFNhân dịp ngày Quốc tế phụ nữ (8-3), các bạn nam trong lớp quyết định mua hoa tặng các bạn nữ trong lớp mình. Tuy nhiên, đây là một kế hoạch tự phát, mỗi bạn nam tự mình đi mua hoa không bàn bạc với bạn khác. Chính vì vậy cuối cùng có \(M\) loại hoa khác nhau được đem đến lớp (các loại hoa đánh số từ 1 đến \(M\)), loại hoa thứ \(i\) có \(a_i\) bông hoa.
Một vấn đề đau đầu được đặt ra cho lớp trưởng - một bạn nam đẹp trai nhất trong lớp- là làm thế nào chia các bông hoa này cho các bạn nữ trong lớp để số bông hoa của bạn nữ nhận được nhiều hoa nhất là nhỏ nhất (bặc biệt là bạn nữ mà lớp trưởng yêu thích). Biết rằng mỗi bạn nữ chỉ nhận các bông hoa cùng một loại (hoặc không nhận được bông hoa nào).
Yêu cầu: Viết chương trình tính số lượng hoa của bạn nữ nhận được nhiều hoa nhất trong phương án trên.
Input
- Dòng đầu tiên ghi hai số nguyên dương \(N\) (\(1 \le N \le 10^9\)) là số lượng bạn nữ trong lớp và \(M\) (\(1 \le M \le 10^6; M \le N\)) là số lượng loại hoa khác nhau
- \(M\) dòng tiếp theo, dòng thứ \(i\) ghi số \(a_i\) là số lượng hoa của loại hoa thứ \(i\) (\(1 \le a_i \le 10^9\))
Output
- Một số nguyên duy nhất là số bông hoa của bạn nữ nhận được nhiều hoa nhất trong phương án tối ưu (là phương án mà số hoa của bạn nữ có nhiều hoa nhất là nhỏ nhất)
Scoring
- Subtask \(1\) (\(50\%\) số điểm): \(n ≤ 10^4\).
- Subtask \(2\) (\(25\%\) số điểm): \(n ≤ 10^6\).
Example
Test 1
Input
5 2
7
4 Output
3Note
- 7 bông hoa đầu chia cho 3 bạn với số lượng là \(3; 2; 2\);
- 4 bông hoa đầu chia cho 2 bạn với số lượng là \(3; 1\) hoặc \(2; 2\);
Test 2
Input
7 5
7
1
7
4
4 Output
4
Bình luận
tại sao chữ đẹp trai lại in hoa thế kia ạ ?????
Có liên quan đến ai thì người nấy quan tâm.
em quan tâm vậy em là người đẹp tai đúng không ạ :)))
AC = đẹp trai. Bạn AC chưa?