LQDOJ Contest #10 - Bài 4 - Chia Kẹo

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
shiba
Dạng bài
Điểm: 1200 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Vào ngày sinh nhật của LQDOJ, shiba - một thành viên của Team Shiba quyết định tặng kẹo cho các bạn trẻ trong trường. Có \(N\) đứa trẻ muốn được nhận kẹo và shiba có một bịch kẹo gồm \(M\) vị khác nhau. Có một điều khiến shiba phải băn khoăn rằng tất cả đứa trẻ muốn tất cả viên kẹo mà mình có đều phải có cùng một vị. shiba cũng biết rằng các bạn trẻ sẽ ghen tị nếu có một bạn được quá nhiều kẹo. Để giải quyết các điều này một cách êm đềm nhất, shiba quyết định chia kẹo sao cho mức độ ghen tị sẽ là nhỏ nhất có thể, biết rằng mức độ ghen tị là số kẹo nhiều nhất mà một bạn trẻ có được.

Ví dụ bịch kẹo của shiba có \(7\) viên kẹo vị \(X\) và \(4\) viên kẹo vị \(Y\) thì mà cần chia cho \(5\) đứa trẻ thì shiba có thể chia như sau: \(XX\),\(XX\),\(YY\),\(YY\),\(YYY\). Mức độ ghen tị lúc này là \(3\), là mức độ ghen tị nhỏ nhất có thể.

Tuy nhiên thực hiện việc chia kẹo là quá khó với shiba. Anh ấy nhờ các bạn lập trình tài năng của LQDOJ giúp shiba tìm cách chia sao cho mức độ ghen tị là nhỏ nhất có thể.

Yêu cầu: Bạn hãy giúp shiba tính mức độ ghen tị nhỏ nhất có thể. Biết rằng trường hợp có đứa trẻ không nhận được một viên kẹo nào là có thể xảy ra.

Input

  • Dòng đầu tiên chứa hai số nguyên dương lần lượt là \(N\) và \(M\) \((1 \le N \le 10^9,1 \le M \le 3 \times 10^5, M \le N)\).
  • \(M\) dòng tiếp theo mỗi dòng chứa một số nguyên dương là số kẹo của từng vị mà shiba có. Số kẹo của từng vị nằm trong đoạn \([1;10^9]\).

Output

  • In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài.

Scoring

  • Subtask \(1\) (\(20\%\) số điểm): Có \(N \le 25\).
  • Subtask \(2\) (\(80\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input 
5 2
4
7
Output 
3
Note

Ví dụ đã được giải thích ở trên.

Bình luận


  • 2
    blinh    11:48 p.m. 9 Tháng 9, 2024 ← chỉnh sửa 6
    summary

    hint: sử dụng tìm kiếm nhị phân rồi xét kết quả
    vd:
    5 2
    4
    7
    sử dụng định lý dirichlet nếu
    -mức độ ghen tị là 3 thì ta có thể chia: AAA, A, BBB, BBB, B => thỏa
    -mức độ ghen tị là 4 thì ta có thể chia: AAAA, BBBB, BBB (còn dư 2 đứa :v) => loại => xét đến kết quả thấp hơn
    -mức độ ghen tị là 2 thì ta có thể chia: AA, AA, BB, BB (còn dư 3 cái kẹo còn lại) => loại => xét kết quả cao hơn

    CODE AC PYPY(PYTHON) 
    a,b=map(int,input().split())
ds=[]
res=-1
for i in range(b):ds.append(int(input()))
l,r=1,int(max(ds))
def check(n):
    ans=0
    for i in ds:
        t=i//n
        if t<i/n:t+=1
        ans+=t
    if ans<=a:return True
    else:return False
while l<=r:
    mid=(l+r)//2
    if check(mid):
        res=mid
        r=mid-1
    else:l=mid+1
    #print(mid)
print(res)
      • 3 bình luận nữa