题解 P1873 【砍树】

Mcggvc · 2019-03-10 23:06:48 · 题解

题目链接：P1873 砍树

这道题并不需要二分（其实是我不会）暴力枚举就可以过

我们先将树的高度由大到小排序，定义答案ans初始为最高的树的高度，当目前获得树木长度小于M米时，执行：

1.锯片高度(ans)下降一米

2.当前获得树木长度(lon)+=之前可以砍到的树的数量+降低高度后可以砍到树的数量（因为每次只会下降1m）

3.判断lon是否大于M

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define ll long long 
using namespace std;
ll n,m;
ll tre[1000100];
bool cmp(ll a,ll b){return a>b;} //降序
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>tre[i];
    sort(tre+1,tre+n+1,cmp); 
    ll lon=0；//lon：当前得到的木材长度
    ll tot=0;//tot：当前可以砍到的树的数量
    ll ans=tre[1],i=1;//ans：锯片高度
    while(lon<m&&i<=n)
    {
        ans--;
        while(tre[i]>ans) 
        {
            i++;
            tot++;
        }
        lon+=tot;
        if(lon>=m) break;
    }
    cout<<ans;
    return 0;   
}

再次膜拜ZCJ dalao