自动搬运

查看原文

来自洛谷，原作者为

	NightStriker .

搬运于2025-08-24 22:43:31，当前版本为作者最后更新于2022-12-21 18:40:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

（1.16：本题解进行了一些修改，希望管理能给通过 /kel）

题意：

有 $N$（$1 \le N \le 10^5$）头奶牛可能会入学。每头奶牛最多愿意支付 $c_i$ 的学费（$1 \le c_i\le 10^6$）。 Farmer John 可以设定所有奶牛入学需要支付的学费。如果这笔学费大于一头奶牛愿意支付的最高金额，那么这头奶牛就不会入学。Farmer John 想赚尽可能多的钱，从而可以给他的讲师提供一笔可观的工资。请求出他能赚到的钱的数量，以及此时应当收取多少学费。

$33$ 分做法

虽然是 T1，但是纯暴力是过不去的哦。

枚举答案，然后再遍历一遍数组判断当前奶牛能否支付起现在的学费，不断取 $\operatorname{max}$ 就行了。

设 $k$ 是 $c_i$ 中最大的数字，这种暴力的做法时间复杂度即 $\mathcal{O}(nk)$，因为 $k \le 10^6$，所以明显会 TLE。

放一下代码吧。

#include<iostream>
#define int long long//不开ll见祖宗（
using namespace std;
int n,a[100001],ans,k,cnt,mx;
signed main(){
	cin>>n;
	for(int i = 1;i<=n;i++) {
		cin>>a[i];
		k = max(k,a[i]);
	}
	for(int i = 1;i<=k;i++){//枚举答案
		ans = 0;
		for(int j = 1;j<=n;j++){
			if(a[j]>=i) ans+=i;//判断第 j 头奶牛能否支付起当前的学费 i
		}
		if(ans>mx){//打擂台取最大
			mx = ans;
			cnt = i;
		}
		if(ans==mx){//如果答案相同取学费小的
			cnt = min(cnt,i);
		}
	}
	cout<<ans<<' '<<cnt<<endl;
	return 0;
} 

$100$ 分做法（满分）

可以证明，取的最佳学费永远是 $c_i$ 的其中之一（因为如果不是，可以稍微增加学费而不改变付钱的牛）。

因此，我们所要做的就是维护这些值，看看每个值能赚多少钱。

我们先排一下序，确定有多少奶牛可以支付当前的学费，然后从最低到最高进行更新，维护愿意支付的奶牛数量的计数。（在一个 $c_i$ 值被遍历到后，这些奶牛就不再能够支付学费，所以计数是递减）

这些操作在 $\mathcal{O}(n \log n)$ 的时间复杂度就可以解决力（喜

还有最重要的一件事，就是 不开 $\textbf{long long}$ 见祖宗，因为答案可能高达 $10^5 \times 10^6 = 10^{11}$。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,a[1000001],ans,cnt;
signed main() {
	cin>>n;
	int cow = n;
	for (int i = 1; i<=n; i++) cin>>a[i];
	sort(a+1,a+n+1);
	for (int i = 1; i<=n; i++) {
		if (a[i]*cow>ans) {//最优答案更新 
			ans = a[i]*cow;
			cnt = a[i];
		}
		cow--;//第i-1头牛不交学费了。 
	}
	cout<<ans<<' '<<cnt<<endl;
	return 0;
}

一些魔怔的废话：作者因为评测机原因这道题抱灵力！谢谢你，USACO。