2861: 练55.3 收益最大

内存限制：64 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：2 解决：2

题目描述

农夫John 余下了$m$批干草无法处理，他准备要开一个拍卖会去出售他的干草。现在有$n$个顾客，每个顾客的报价是$a_i$。现在John要确定一个单价，所有报价大于等于单价的顾客将会买到$1$批干草($m$批干草不用全卖完)，总共获得的金钱作为收益。那么问题来了，如何设定单价，使得收益最大。

输入

第一行两个整数$m$,$n$，分别表示$m$批干草和$n$个顾客。第二行$n$个整数，$a_i$表示第$i$个顾客的报价。
数据范围:$1 < n, m ≤1000$，$1 < a_i ≤ 10000$。

输出

两个用空格分隔的整数，分别表示单价和总收益。如果有多个相等的最大收益，选取单价最小的那个。

样例输入 复制 

5 4
2 8 10 7

样例输出 复制 

7 21

提示

#include<bits/stdc++.h>
using namespace std;
int grass,n,a[1004],ans,cnt,prize;
int main(){
    cin>>grass>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1,greater<int>());
    for(int i =1;i<=n;i++){
        cnt=min(i,grass);
        if(ans<=cnt*a[i]){
            ans=cnt*a[i];
            prize=a[i];
        }
    }
    cout<<prize<<' '<<ans;
    return 0;
}

来源/分类

提交提交记录统计露一手!