NKOJ1363-砍树
目录
问题描述
N棵树,每棵都有一个整数高度。有一个木头的总需要量M。
现在确定一个最大的统一的砍树高度H,如果某棵树的高度大于H,则高出的部分被砍下。使得所有被砍下的木材长度之和达到M(允许稍超过M)。
例如,有4棵树,高度分别是20 15 10 17, 需要的木材长度为 7,砍树高度为15时,第1棵树被砍下5,第4棵树被砍下2,得到的总长度为7。如果砍树高度为16时,第1棵树被砍下4,第4棵树被砍下1,则得到的木材数量为5。
输入格式
第1行:2个整数N和M,N表示树木的数量(1 ≤ N ≤ 1 000 000),M表示需要的木材总长度(1 ≤ M ≤ 2 000 000 000)。
第2行: N个整数表示每棵树的高度,值均不超过1 000 000 000。所有木材高度之和大于M,因此必然有解。
输出格式
第1行:1个整数,表示砍树的最高高度。
样例输入
5 20
4 42 40 26 46
样例输出
36
思路一
一道标准的二分答案题,目标是把砍树高度的范围从1~最高的数的高度-1缩小到一个确定的值。那么我们只需要先进行排序,再二分找出能达到砍下M段木材的最大H值,就可以秒了它!!!
发起进攻!(NKOJ竟然方法一用时更少,一时无语)
代码一
#include<bits/stdc++.h>
using namespace std;
long long n,m,l=0,maxheight=1,r,mid,a[1000001];//当然也可以用unsigned long
bool checkR(long long pos){
long long cnt=0;
for(int i=1;i<=n;i++)
if(a[i]>pos)
cnt+=a[i]-pos;//按pos能砍多少树
return cnt>=m;//就是true和false
}
int main(){//二分答案:找到缩小答案范围的方法
scanf("%lld%lld",&n,&m);
for(long long i=1;i<=n;i++){
scanf("%lld",&a[i]);
maxheight=max(maxheight,a[i]);//保存最高的树的高度
}
maxheight--; //按最高的树的高度砍,什么都砍不到,故-1
r=maxheight;
while(l<r){//答案范围(相等就确定了)
mid=(l+r+1)/2; //要尽量就向高取以免漏过某个高度 (当然,姑且相信砍树高度是整数【虽然事实也是这样】)
if(checkR(mid)) //如果mid砍得出来
l=mid; //贪心的考虑上面还有没有砍更高的
else //mid砍不出来
r=mid-1; //砍得比mid低
}
printf("%lld",l);//此时l==r,输出谁都一样
return 0;
}
思路二
每次按从大到小的树的高度讨论,当出现>需求的时候,把大于的部分按前面以讨论的树的数量取平均值,得到答案
代码二
#include<bits/stdc++.h>
using namespace std;
long long a[1000001],n,m,num,ans,sum;
int main(){
scanf("%lld%lld",&n,&m);
for(long long i=1;i<=n;i++)
scanf("%lld",&a[i]);
sort(a+1,a+n+1);//从小到大排序
num=n;//从n开始讨论
for(;sum<m;num--)//直到砍下的>需求时退出
sum+=(a[num]-a[num-1])*(n-num+1);//每次从大到小按树的高度讨论
//(a[num]-a[num-1]):相较于上一个高度每棵多砍了多少
// (n-num+1):有n-(num-1)棵被砍【其实当前讨论的是第num-1棵,因为按第n棵是什么都砍不到的】
//此时可以确定,要砍的高度一定在num与num-1之间【因为退出循环前num多减了一次1,但sum却还保持在没有减1的num对应的值】
//我们就可以用 第num棵树的高度加上sum比需求多出的数量 除以 n到num的树数 得到结果
ans=a[num]+(sum-m)/(n-num);
printf("%lld",ans);
return 0;
}
版权声明:本文为mRXxy0o0原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。