Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AUCTION - Going Once, Going Twice, Gone!

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/auction


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


Được gửi lên bởi:Phong
Ngày:2008-11-11
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM qobi ST WHITESPACE
Nguồn bài:USACO November 2008

hide comments
2021-05-27 17:59:33
Tham khảo: https://vnspoj.github.io/problems/AUCTION
2020-12-26 05:53:40
cho em hỏi làm hơn O(n) kiểu gì ạ
2020-06-25 04:35:48
trâu AC nhé, gáy lên
2019-09-10 15:24:08
Bài khó quá phải dùng bfs + hash + sort + dijkstra + qhđ + it + lca +hld mới full được :)(()

2019-01-02 09:29:58
1 đấm ac from Lào Cai
2019-01-02 09:14:39
DCM O(1) easy vcl!
2019-01-02 09:14:20
Bài này dùng dp + hash + một chút toán học. Độ phức tạp chỉ O(1) thôi
2019-01-02 08:50:07
Có lồn trâu mà AC ý, địt mẹ mày bố thử rồi;
Nguyễn Cường Lào Cai vô đối;

2018-12-03 15:36:25
hello xin chao tat ca cac ban
2018-08-23 17:58:10
Nếu có sort rồi thì là O(nlogn) rồi chứ ko phải O(n) nữa, còn nếu bác nào làm O(n) thật thì quả là cao thủ !
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.