Vét Cạn | Lập Trình C/C++ | Trang 2
Có thể bạn quan tâm
Chế độ ăn kiêng của đàn bò khiến cho nông trang của nông dân John dôi ra 1 số lượng cỏ khô, vì vậy anh ta muốn bán đấu giá số cỏ khô này để trang trải phần nào chi phí chăn nuôi. Anh ta có N (1 <= N <= 1,000) bó cỏ khô giống nhau; khách hàng sẽ đấu giá để mua đống cỏ này là M (1 <= M <= 1,000) nông dân khác sống gần đó.
Mỗi một nông dân i sẽ cho nông dân John biết anh ta sẵn sàng trả P_i (1 <= P_i = mức giá đó, những người còn lại sẽ bị từ chối giao dịch.
Hãy giúp nông dân John tính xem đặt mức giá nhỏ nhất là bao nhiêu để thu được nhiều tiền nhất có thể. Dữ liệu
* Dòng 1: Hai số nguyên cách nhau bởi dấu cách: N và M
* Dòng 2..M+1: Dòng i+1 chứa 1 số nguyên duy nhất: P_i Kết quả
* Dòng 1: 2 số nguyên cách nhau bởi dấu cách: giá bán của John và số tiền mà John thu được Ví dụ
Dữ liệu: 5 4 2 8 10 7
Kết quả: 7 21
Nguồn: http://vn.spoj.com/problems/AUCTION/
Hướng dẫn: Thuật giải tham lam theo nguyên lý thứ tự vét cạn các khả năng 1. Bước 1 sắp xếp p1…pm giảm dần dùng hàm sort có sẵn chú ý phải viết thêm hàm so sánh để giảm dần 2. Số bó cỏ bán tối đa sẽ là min(n,m) nên nếu m>n thì m gán lại bằng n 3. Xét lần lượt số bỏ có được bán từ 1 đến m ta tìm max của i*p[i] chú ý bài toán tìm giá nhỏ nhất nên nếu có nhiều max thì ta chọn max có p[i] nhỏ nhất
code
#include<algorithm> #include<stdio.h> using namespace std; long ss(long x,long y) {return x>y;} int main() { int n,m,t=1; long p[1005]; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%ld",&p[i]); sort(p+1,p+1+m,ss); if(m>n) m=n; for(int i=2;i<=m;i++) if(i*p[i]>=t*p[t]) t=i; printf("%d %ld",p[t],t*p[t]); }Chia sẻ ngay:
Đang tải...Từ khóa » Thuật Toán Vét Cạn Là Gì
-
Tìm Kiếm Vét Cạn (Complete Search) - Vallicon
-
Những Cách Tiếp Cận Bài Toán: Phần 2 - VNOI
-
CHIẾN LƯỢC VÉT CẠN VÀ THUẬT TOÁN ĐỆ QUY - Quê Hương
-
Thắc Mắc Về Thuật Toán Vét Cạn - Programming - Dạy Nhau Học
-
Thuật Toán Vét Cạn Là Gì? Đưa Ra Một đề Bài Và Bài Giải - MTrend
-
Vấn đề Vét Cạn Và Giải Pháp
-
Chuyen De Vet Can - DocShare.tips
-
[PDF] Phân Tích Thiết Kế Giải Thuật - Cit..vn
-
Cả Nhà Ai Biết Về Thuật Toán "VÉT CẠN" Giúp Tôi Với. - Tối ưu Hóa
-
Đề Tài: Thiết Kế Thuật Toán Vét Cạn Và Tham Lam - Tài Liệu Text - 123doc
-
Thuật Toán Vét Cạn Là Gì? Đưa Ra Một đề Bài Và Bài Giải