题目描述
某拍卖行计划出售一批限量版收藏品。他们共有N件相同藏品(1≤N≤1000),收到M位收藏家(1≤M≤1000)的竞拍意向。每位收藏家提交了自己愿意为单件藏品支付的最高价格。拍卖行需要设定一个统一的成交价,所有出价不低于该价格的收藏家都将成功购得藏品,但售出总量不得超过库存量N。请为拍卖行确定一个既能获得最大收益,又尽可能降低成交价的最优定价策略。
输入格式:
第一行:两个整数,分别表示藏品总数N和收藏家数量M
第二行到第M+1行:每行一个整数,表示第i位收藏家的出价
输出格式:
第一行:两个由空格分隔的整数,分别表示最优成交价和对应总收益
输入样例#1:
5 4
2
8
10
7
输出样例#1:
7 21
样例解释:
输入样例解释:
拍卖行拥有5件藏品,4位收藏家出价分别为2、8、10、7。设定成交价为7时,出价≥7的三位收藏家(报价8、10、7)将各购得1件,共售出3件,总收益7×3=21元,这是所有可能定价中的最大收益且最低可行价格。