【寒假每日一题】AcWing 4818. 奶牛大学（补）

一、题目

1、原题链接

4818. 奶牛大学

2、题目描述

Farmer John 计划为奶牛们新开办一所大学！ 有 N 头奶牛可能会入学。 每头奶牛最多愿意支付 ci 的学费。 Farmer John 可以设定所有奶牛入学需要支付的学费。 如果这笔学费大于一头奶牛愿意支付的最高金额，那么这头奶牛就不会入学。 Farmer John 想赚尽可能多的钱，从而可以给他的讲师提供一笔可观的工资。 请求出 他能赚到的钱的数量，以及此时 应当收取多少学费。 输入格式 输入的第一行包含 N。 第二行包含 N 个整数 c1,c2,…,cN，其中 ci是奶牛 i 愿意支付的最高学费金额。 输出格式 输出 Farmer John 可以赚到的最大金额以及最优情况下他应该收取的学费。如果有多个解，输出收取学费最小的解。 注意这个问题涉及到的整数可能需要使用 64 位整数型（例如，Java 中的 “long”，C/C++ 中的 “long long”）。 数据范围1≤N≤10⁵,1≤ci≤10⁶。 输入样例：

4 1 6 4 6

输出样例：

12 4

样例解释 如果 Farmer John 收费 4，那么 3 头奶牛将会入学，从而使他赚取 3×4=12的金额。

二、解题报告

思路来源： AcWing 4818. 奶牛大学（寒假每日一题2023） y总yyds

1、思路分析

(1)我们可以先将每头奶牛愿意支付的费用进行排序。 (2)如果收取的学费没有超过奶牛愿意支付的费用，则奶牛可以入学。求取入学奶牛数量就转化为了要求取奶牛愿意支付的费用序列中大于等于学费的个数，而学费可以不是整数。在奶牛入学数量一定时，我们希望学费在能满足这个入学数量的情况下，越大越好，也就是让学费恰好和当前入学数量中愿意支付钱数最少的那个奶牛所愿支付的钱数相等。而如果不是这样的话，我们的学费一定不是在满足这样入学数量时最大的。 (3)问题就转换成了：我们枚举(1)中序列的各个费用分别作为学费，来求此时的收益，其中收益最大即为所求，而学费就是求得此收益的学费。

2、时间复杂度

时间复杂度为O(n)

3、代码详解

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=100010;
LL c[N],n;
int main()
{   cin>>n;
    for(int i=0;i<n;i++){
    	cin>>c[i];
	}
	sort(c,c+n);
	LL ans=0,sum=0,p;
	for(int i=0;i<n;i++){
	   sum=(n-i)*c[i];
	   if(sum>ans){
	     ans=sum;	 
	   	 p=c[i];
	   }
	}
	cout<<ans<<" "<<p;
    return 0;
}