luogu P1873 [COCI 2011/2012 #5] EKO / 砍树

题目大意

有正整数 $N,M$ 和 $N$ 棵树，第 $i$ 棵树的高度为正整数 $a_i$。求一个最大的正整数 $ans$，使得所有树中高度超过 $ans$ 的部分的高度之和不小于 $M$。

解题思路

一种显然的思路是，二分枚举 $ans$，再分别检验答案是否合理。为了检验便捷，需对 $a_i$ 排序。时间复杂度 $O(N{\log }_{2}N+{\log }_{2}M)$。病历本：类型转换。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

const int MAXN=1000010;
typedef long long ll;

int n, m;
int e[MAXN];
int bk[MAXN], d[MAXN];
ll sum[MAXN];

inline int read (){
	int s=0; char c;
	do c=getchar (); while ('0'>c||'9'<c);
	while ('0'<=c&&'9'>=c)
		s=s*10+c-'0', c=getchar ();
	return s;
}
int main(){
	n=read (); m=read ();
	for (int i=1; i<=n; ++i)
		e[i]=read ();
	std::sort (e+1, e+n+1);
	//discretize
	int cnt=0, last=-1;
	for (int i=1; i<=n; ++i){
		if (e[i]!=last) ++cnt;
		++bk[cnt]; d[cnt]=e[i];
		last=e[i];
	}
	sum[0]=0; e[0]=0;
	for (int i=1; i<=n; ++i)
		sum[i]=e[i]+sum[i-1];
	//锯掉哪些树 
	int left=1, right=n, mid, ans=-1;
	while (left<=right){
		mid=(left+right)/2;
		if (sum[n]-sum[mid]-(ll)(n-mid)*(ll)e[mid]>=m)
			ans=mid, left=mid+1;
		else right=mid-1;
	}
	//从哪锯 
	left=e[ans]; right=e[ans+1]-1;
	ll count=sum[n]-sum[ans];
	int length=n-ans; ans=-1;
	while (left<=right){
		mid=(left+right)/2;
		ll tmp=count-(ll)mid*(ll)length;
		if (tmp>=m)
			ans=mid, left=mid+1;
		else right=mid-1;
	}
	printf ("%d", ans);
}

如果不枚举从哪棵树开始锯，则时间复杂度变为 $O(N{\log }_{2}N+{\log }_{2}N{\log }_{2}M)$，同样可以接受。

“从哪开始锯"的部分也可以通过数学计算算出。则时间复杂度变为 $O(N{\log }_{2}N)$。