Mô tả
Đội frontend của VNG đang chuẩn bị nâng cấp quy tắc kiểm tra mã nguồn (ESLint) cho hàng loạt kho mã (repo). Mỗi repo có một khối lượng cấu hình khác nhau, được đo bằng số dòng cấu hình cần viết.
Do giới hạn nhân lực, giám sát kỹ thuật quyết định: trong đợt này, tổng số dòng cấu hình của các repo được chọn nâng cấp không được vượt quá q. Mục tiêu của đội là nâng cấp cho nhiều repo nhất có thể.
Bạn được giao nhiệm vụ: cho danh sách khối lượng cấu hình của từng repo và ngưỡng q, hãy tìm số lượng repo lớn nhất có thể chọn sao cho tổng khối lượng cấu hình không vượt quá q.
Đầu vào
- Một mảng số nguyên dương
c(độ dài từ 1 đến 1000), trong đóc[i]là số dòng cấu hình của repo thứ i. - Một số nguyên dương
q(1 ≤ q ≤ 10^6), là tổng số dòng cấu hình tối đa được phép.
Dữ liệu vào được truyền dưới dạng hai tham số: mảng c và số q.
Đầu ra
- Trả về một số nguyên không âm: số lượng repo nhiều nhất có thể chọn nâng cấp mà tổng khối lượng cấu hình không vượt quá q.
Ràng buộc
- 1 ≤ độ dài mảng c ≤ 1000
- 1 ≤ c[i] ≤ 10^4
- 1 ≤ q ≤ 10^6
Ví dụ
Ví dụ 1:
Đầu vào: c = [3, 1, 4, 1, 5], q = 7
Giải thích: Sắp xếp khối lượng cấu hình theo thứ tự tăng dần: [1, 1, 3, 4, 5]. Chọn lần lượt repo nhỏ nhất trước: 1 + 1 + 3 = 5 ≤ 7 (chọn được 3 repo). Nếu thêm repo tiếp theo có khối lượng 4, tổng là 9 > 7, không thỏa mãn. Vậy đáp án là 3.
Đầu ra: 3
Ví dụ 2:
Đầu vào: c = [5, 5, 5], q = 3