Nguồn đề bài: AUCTION
1. Đề bài AUCTION spoj
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 <= 1,000,000) đồng cho 1 bó cỏ khô. Mỗi một nông dân chỉ muốn mua 1 bó cỏ khô mà thôi. Để đảm bảo các nông dân không ghen tị với nhau, nông dân John sẽ đưa ra 1 mức giá cố định cho tất cả người đến mua và bán các bó cỏ khô cho những ai trả giá >= 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
2. Code tham khảo AUCTION spoj
lưu ý 2 code mẫu dưới đây cách làm là khác nhau
a. Code pascal
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 | program sdsdsd; const fi=''; type dayso = array[1..1000] of longint; var n,m,vtmax:longint; i,max:longint; a:dayso; f:text; function tinh(vt:longint):longint; var i:longint; s:longint; begin if m-vt+1>n then exit(a[vt]*n); exit(a[vt]*(m-vt+1)); end; procedure sort(l,r: longint); var i,j,x,y: longint; begin i:=l; j:=r; x:=a[(l+r) div 2]; repeat while a[i]<x do inc(i); while x<a[j] do dec(j); if not(i>j) then begin y:=a[i]; a[i]:=a[j]; a[j]:=y; inc(i); j:=j-1; end; until i>j; if l<j then sort(l,j); if i<r then sort(i,r); end; begin assign(f,fi); reset(f); readln(f,n,m); for i:= 1 to m do read(f,a[i]); close(f); sort(1,m); max:=tinh(1); vtmax:=a[1]; for i:= 2 to m do if max<tinh(i) then begin max:=tinh(i); vtmax:=a[i]; end; writeln(vtmax, ' ',max); end. |
b. Code C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | #include <bits/stdc++.h> using namespace std; int n,m; vector<int> a; void Init() { cin>>n>>m; a.resize(m); for (int i=0;i<m;i++) { cin>>a[i]; } } void Solve() { int res=0; int gia=0; for (int i=0;i<m;i++) { int sum=0; for (int j=0;j<m;j++) { if(a[j]>=a[i]) sum+=a[i]; } sum=min(sum,n*a[i]); if(sum==res) gia=min(gia,a[i]); if(sum>res) { res=sum; gia=a[i]; } } cout<<gia<<" "<<res; } int main() { Init(); Solve(); } |
Bài viết liên quan
- PTIT016D spoj PTIT- ACM PTIT 2016 D – Biểu thức
- P151PROG spoj PTIT – Xếp Hàng
- CBUYING spoj – Chocolate Buying
- P167PROE spoj PTIT – ROUND 7E – Phương trình
- PTIT016E spoj PTIT – ACM PTIT 2016 E – Kỳ thi ACM/ICPC
- Spoj PTIT PTIT016C – ACM PTIT 2016 C – Chẵn lẻ
- PTIT127A spoj PTIT – Tổ chức kì thi
- P164SUMI spoj PTIT – ROUND 4I – Next round
- PTIT135J spoj PTIT – Tính lãi suất
- P156SUME spoj PTIT – ROUND 6E – Ước chung của chuỗi