Một chiếc cặp có thể chứa rất nhiều viên bi với các loại màu khác nhau. Cho mảng arr chứa số lương bi của các loại bi đó, đếm số bi cần lấy ra tối thiểu để chắc chắn có được n loại. Nếu không thể tìm ra đáp án, trả về -1 .
Đếm số bi cần lấy ra tối thiểu để chắc chắn có được n loại
Áp dụng Đi-dép-lê:
số bi cần lấy ra tối thiểu để chắc chắn có được n loại là
max\left(\sum_{j=0}^{n-1} arr[i_j] + 1\right)
Đi-dép-lê là ai
Công thức trên cũng không hẳn là Đi-dép-lê, nhưng chắc chắn rằng có thể viết lại bằng
ans = \sum_{i=0}^{n-1} arr[i] + 1
với mảng arr xếp giảm dần.
Còn tại sao có công thức trên thì bạn phải tự nghĩ.
3 Likes
cho em xin code ạ em còn yếu :((
Code đây:
FAQ
print("Tự code đi bạn ơi")
print(sum(sorted(map(int, input().split())[-n+1:]) + 1)
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?