思路:
首先看数据范围 2e5,比较大。而且有一个不变的是 我们每次都从最高的竹子区间开始砍,那么每进行一次砍操作,接着还得再找出最高的竹子区间,代表要有多次排序,所以自然而然想到了一个数据结构:堆。
想到 堆 思路就打开了。
可以用pair存高度和编号,也可用结构体,我习惯用结构体,所有这次用结构体排序来解题,想看pair实现的可以移步 大佬的题解。
结构体自写运算符重载,在这里格式要写对了:const一个也不能少
typedef long long ll;
struct node
{
ll h;
int num;
bool operator <(const node &rhs) const
{
if(h==rhs.h) return num>rhs.num;
return h<rhs.h;
}
};
然后每次找出最高的竹子,因为编号也是有序的,所以直接把相同高度且编号连续的竹子依次取出,然后把竹子砍一半再加入堆中。
结束条件很明显,最高的竹子的高度是1就代表我们已经结束了。
但这道题中 sqrt函数对于long long 类型数据计算会有误差,所以要么自己重载sqrt函数,或者用sqrtl函数,否则将一直卡在65%,有部分点过不了。
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node
{
ll h;
int num;
bool operator <(const node &rhs) const//运算符重载
{
if(h==rhs.h) return num>rhs.num;
return h<rhs.h;
}
};
priority_queue<node> q;
int main()
{
int n,ans=0;
ll t;
cin>>n;
for(int i=1;i<=n;i++)//一开始全都加入堆
{
scanf("%lld",&t);
q.push((node){t,i});
}
while(q.top().h!=1)//最高的竹子高度为1那么肯定都砍完了结束
{
t=q.top().h;//取出最高竹子的高度和编号
n=q.top().num-1;
while(q.top().h==t&&q.top().num==n+1)//把高度相同且编号连续的竹子砍完再入堆
{
n++;
q.pop();
q.push((node){sqrtl(t/2+1),n});
}
ans++;
}
cout<<ans;
return 0;
}