Ba lô phân số

Buổi 12 — Greedy Algorithm greedy sorting
Points
16
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Submissions
Đề bài

Một tên trộm đột nhập vào kho báu có $N$ loại vật phẩm. Vật phẩm thứ $i$ có tổng khối lượng $w_i$ và tổng giá trị $v_i$. Chiếc ba lô của tên trộm chỉ chứa được tối đa khối lượng $W$. Khác với bài toán ba lô thông thường, tên trộm có thể lấy một phần bất kỳ (phân số) của một vật phẩm với giá trị tỉ lệ thuận theo khối lượng lấy được. Hãy tìm tổng giá trị lớn nhất mà tên trộm có thể mang đi.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N$ và $W$.
  • $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $w_i$ và $v_i$.
Dữ liệu ra

Một số thực duy nhất là tổng giá trị lớn nhất có thể, làm tròn đến đúng 2 chữ số thập phân.

Ví dụ
Input Output
3 50\n10 60\n20 100\n30 120 240.00
1 10\n20 100 50.00
Giới hạn
  • $1 \le N \le 10^5$
  • $1 \le W \le 10^9$
  • $1 \le w_i, v_i \le 10^6$
Draft saved