奶牛大学(2023寒假每日一题 1)
阿里云国内75折 回扣 微信号:monov8 |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |
Farmer John 计划为奶牛们新开办一所大学有 N N N 头奶牛可能会入学。
每头奶牛最多愿意支付 c i c_i ci 的学费。
Farmer John 可以设定所有奶牛入学需要支付的学费。
如果这笔学费大于一头奶牛愿意支付的最高金额那么这头奶牛就不会入学。
Farmer John 想赚尽可能多的钱从而可以给他的讲师提供一笔可观的工资。
请求出他能赚到的钱的数量以及此时应当收取多少学费。
输入格式
输入的第一行包含
N
N
N。
第二行包含 N N N 个整数 c 1 , c 2 , … , c N c_1,c_2,…,c_N c1,c2,…,cN其中 c i c_i ci 是奶牛 i i i 愿意支付的最高学费金额。
输出格式
输出 Farmer John 可以赚到的最大金额以及最优情况下他应该收取的学费。如果有多个解输出收取学费最小的解。
注意这个问题涉及到的整数可能需要使用 64 位整数型例如Java 中的 “long”C/C++ 中的 “long long”。
数据范围
1
≤
N
≤
1
0
5
,
1≤N≤10^5,
1≤N≤105,
1
≤
c
i
≤
1
0
6
。
1≤c_i≤10^6。
1≤ci≤106。
输入样例
4
1 6 4 6
输出样例
12 4
样例解释
如果 Farmer John 收费
4
4
4那么
3
3
3 头奶牛将会入学从而使他赚取
3
×
4
=
12
3×4=12
3×4=12 的金额。
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
int a[N];
int main(){
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
sort(a, a + n, greater<int>());
LL res = 0, val = 0;
for(int i = 0; i < n; i++){
LL x = (LL)(i + 1) * a[i];
if(res <= x) res = x, val = a[i];
}
printf("%lld %lld\n", res, val);
return 0;
}