#5219. MAXAVERAGE - Tỷ lệ trung bình tối đa

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Cho N vật, vật thứ i có giá trị v_i và trọng lượng w_i . Bạn cần chọn ra chính xác K vật. Hãy tìm cách chọn sao cho tỷ lệ (tổng giá trị) / (tổng trọng lượng) là lớn nhất có thể.

Dữ liệu:

  • Dòng đầu tiên chứa hai số nguyên N K ( 1 \le K \le N \le 10^5 ).
  • N dòng tiếp theo, mỗi dòng chứa hai số nguyên v_i w_i ( 1 \le v_i, w_i \le 10^9 ).

Kết quả: In ra một số thực duy nhất là tỷ lệ (tổng giá trị) / (tổng trọng lượng) lớn nhất. Kết quả được làm tròn đến hàng phần trăm.

Ví dụ:

Dữ liệu:

3 2
10 2
5 3
8 4

Kết quả:

3.00

Giải thích: Chọn vật 1 và vật 3. Tỷ lệ là (10+8)/(2+4) = 18/6 = 3 .

Giới hạn:

  • 1 \le K \le N \le 10^5
  • 1 \le v_i, w_i \le 10^9