砍树

题解

我们记总长度为,则需保留的高度为。我们将所有的树排序。每棵树枚举保留的高度即可。

源码

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream> 
#include<algorithm>
#include<stack>
#include<vector>
using namespace std;
typedef long long LL;
const int INF=0x3f3f3f3f;
LL m,n,sum,h[1000005]; 
/*#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<22,stdin),p1 == p2)?EOF:*p1++)
char buf[(1<<22)],*p1=buf,*p2=buf;*/
#define gc() getchar()
template<typename _T>
inline void read(_T &x)
{
	int f=1;x=0;char s=gc();
	while(s>'9'||s<'0'){if(s=='-')f=-1;s=gc();}
	while(s>='0'&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=gc();}
	x*=f;
}//读优
int main()
{
	read(n);read(m);
	for(int i=1;i<=n;i++)
		read(h[i]),sum+=h[i];
	sort(h+1,h+n+1);
	LL q=sum-m,height=0;
	for(LL i=1;i<=n;i++)
	{
		if(q>=(n-i+1)*(h[i]-h[i-1]))
			q-=(n-i+1)*(h[i]-h[i-1]),height+=(h[i]-h[i-1]);//枚举一定可以全保留的树
		else
		{
			height+=q/(n-i+1);
			q-=q/(n-i+1)*(n-i+1);
			break;	
		}//找到需要砍的高度
		if(!q) break;
	}
	printf("%lld",height);
	return 0;
}

谢谢！！！