自动搬运

查看原文

来自洛谷，原作者为

	huangboming 哈哈中二与正义的伙伴吗？

搬运于2025-08-24 22:30:59，当前版本为作者最后更新于2024-08-02 20:11:45，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

前言

我有一个不用二分，极其简单的方法。

题意

给一个序列 $a$，你可以操作 $K$ 次，每次将至多 $L$ 个数字 $+1$ ，求最大的 $h$ 指数，$h$ 指数为有至少 $h$ 个 $a_i \leq h$。如 1 1 2 2 3 这里最大的 $h$ 指数为 $2$。因为有 $3$ 个大于等于的数，分别为 2 2 3，而且 $3>2$，所以成立。而 $3$ 不行因为只有 $1$ 个大于等于的数 3，而且 $1<3$，所以 $h$ 为 $3$ 不行。

分析

首先，我们观察题意。

我们不难发现，题目想我们这么做：

1. 当 $\ge h$ 的数的个数不 $\ge h$ 个时。
2. 先算出在序列中小于 $h$ 的同时最大的 $h-o$ 个数（$o$ 为大于 $h$ 的数的个数）。
3. 将这 $h-o$ 个数的数字大小加起来，叫做 $sum$。
4. 算出 $h \times (h-o)$ 即所需大小的总和减 $sum$ 的值，叫做 $sumi$。
5. 最后比较 $sumi$ 与 $k$，$l$ 大小关系，看一下操作数量够不够。

那么如何用最短的时间求最大的 $h$ 呢?

1. 我们可以先 sort 排序数列保证有单调性。（从小到大）
2. 后算出前缀和。
3. 从小到大枚举 $h$ 指数，当 $a_i\ge i$ 时代表这个大小的 $h$ 合法，相反则代表需要进行操作使这 $h-o$ 个数加上 $sumi$。$o$ 在第一次 $a_i<i$ 时使其等于 $i$。而后每次向前遍历 $o$ 直到 $a_o>i$。注意这里的 $o$ 无需更改，因为 sort 后的数列有单调性。
4. 最后判断，当 $k$ 要大于等于 $h-o$ 中的最小值，且 $\min(l,n)\times k\ge h\times(h-o)$。如果成立更新 $ans=i$ 即 $h$ 指数。最最后输出 $ans$ 即可。

于是，我们不难调出如下代码。但是，需要注意的是！要特判 $o$ 不为 $0$ 即当我们查找大于当前的 $h$ 的数字的个数（向前遍历）,且要写当 $h$ 指数不变的情况。一般就是 $l=0$ 或是 $k=0$ 即 $k$ 乘上 $l$ 太小了的情况，所以要每次记录更新 $ans$ 即最大的 $h$ 指数。

时间复杂度及其证明

时间复杂度：$O(n \log n)$

证明：用到了 sort 所以极限情况是 $O(n \log n)$，遍历 h 和前缀和只用 $O(n)$，求 $o$ 时每次循环 $o$ 的大小是不定义循环初始值的，一直遍历下去，所以只用 $O(n)$。

本人代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,a[2000005],x,ans,k,l,qzh[200005],m,o;
bool cmp(ll ai,ll bi){
	return ai>bi;
}
int main(){
	cin>>n>>k>>l;
	if(l>n)l=n;//特判l大于n时则多余的为无意义要舍去
	m=k*l;
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	sort(a+1,a+1+n,cmp);//排序数列保证其有单调性（从小到大）
	for(int i=1;i<=n;i++){
		qzh[i]=qzh[i-1]+a[i];
	}//求前缀和
	for(int i=1;i<=n;i++){//从小到大枚举h
		if(a[i]<i){
			for(;a[o]<i&&o;o--){} //求大于h的数有哪些
			if(i*(i-o)-qzh[i]+qzh[o]<=m&&i-a[i]<=k){//判断操作是否够
				ans=i;//更新ans即最大的h指数。
			}
		}
		else {
			ans=i;//更新ans在无需操作时最大的h指数。
			o=i;//记录>h的个数
		}
	} 
	cout<<ans;
	return 0;
}