HSG9 Cần Thơ 2026 - Tưới cây
Xem dạng PDFTrong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Công ty CT được giao nhiệm vụ tưới cây trên một tuyến đường có trồng ~N~ cây xanh. Hàng ngày, cây xanh thứ ~i~ (~i=1..N~) cần một lượng nước tưới là ~a_i~ và mức độ ưu tiên là ~p_i~. Do hệ thống nước gặp sự cố, trong ngày hôm nay công ty chỉ có thể huy động được lượng nước là ~M~. Biết rằng các cây xanh có độ ưu tiên càng cao (~p_i~ càng nhỏ) thì phải được tưới trước. Cây xanh thứ ~i~ được gọi là tưới đầy đủ nếu được tưới đủ lượng nước ~a_i~.
Yêu cầu: Hãy cho biết số lượng cây xanh nhiều nhất được tưới đầy đủ.
Input
- Dòng đầu gồm số nguyên ~N~ và ~M~ (~1 \le N \le 2 \times 10^5~, ~1 \le M \le 10^9~);
- Dòng thứ hai gồm ~N~ số nguyên ~a_i~ (~1 \le a_i \le 10^6~);
- Dòng cuối cùng gồm ~N~ số nguyên ~p_i~ (~1 \le p_i \le N~).
Output
Ghi một số nguyên cho biết số lượng cây xanh được tưới đầy đủ.
Sample Input 1
6 10
5 1 2 2 1 2
1 2 1 1 3 1
Sample Output 1
3
Giải thích: Ưu tiên tưới các cây ở vị trí 1, 3, 4, mất 9 đơn vị nước. Phần nước còn thừa lại (~10-9=1~) sẽ tưới cho cây ở vị trí 6 (do mức ưu tiên ~p_6=1~ nhưng không được tính vì không tưới đủ lượng nước cây cần (cây thứ 6 cần 2 đơn vị nước).
Subtasks
- 30% số test ứng với 30% số điểm có tất cả ~p_i=1~;
- 30% số test ứng với 30% số điểm có ~1 \le p_i \le 10~;
- 40% số test ứng với 40% số điểm còn lại: Không có ràng buộc gì thêm.
Notes
Bài này có 2 cách hiểu đề:
- Nếu các cây có ~p_i~ bằng nhau, ta tưới cây có chỉ số ~i~ nhỏ nhất. Đây là cách hiểu theo giải thích ví dụ.
- Nếu các cây có ~p_i~ bằng nhau, ta tưới cây bất kỳ.
Do đề không ghi rõ ràng, mình đã add checker chấp nhận cả 2 cách hiểu đề này.
Bình luận
include<bits/stdc++.h>
using namespace std; const int N = 1e6+7; int a[N], b[N];
int main(){ iosbase::syncwith_stdio(false); cin.tie(NULL); int n , m, tong = 0, dem = 0; cin >> n >> m; for(int i = 1; i <= n; i++){ cin >> a[i]; } for(int i = 1; i <= n; i++){ cin >> b[i]; } vector <pair<int, int>> pairs(n+1); for(int i = 1; i <= n; i++){ pairs[i] = {b[i], a[i]}; } sort(pairs.begin(), pairs.end()); int i = 1; while(i <= n){ if(tong + pairs[i].second > m) break; tong += pairs[i].second; dem++; i++; } cout << dem; }