唐山网站建设报价,有限责任公司设立条件,网站风格对比信息表,手机连接电脑弹窗wordpressAcWing 4409. 砍竹子 - AcWing
题目描述 题目分析
注#xff1a;sqrtl的范围为long double#xff0c;比sqrt更加精确
使用优先队列维护一段区间#xff0c;如果连续一段相同就合并为一个区间#xff0c;从大到小去枚举#xff0c;每次先取出最大的一段#xff0c;双…AcWing 4409. 砍竹子 - AcWing
题目描述 题目分析
注sqrtl的范围为long double比sqrt更加精确
使用优先队列维护一段区间如果连续一段相同就合并为一个区间从大到小去枚举每次先取出最大的一段双关键字排序第一关键字是v第二关键字是区间的左端点先把堆顶元素取出取完之后能合并的合并在一起合并完之后统一做一次操作即可
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int N 2e5 10;
ll n, res, a[N];
struct node
{ll l, r, h;bool operator (const node x) const{if(h ! x.h)return x.h h;return x.l l;}
};
ll f(ll x)
{return sqrtl(x / 2 1);
}
priority_queuenode q;
int main()
{cin n;for(int i 0; i n; i )cin a[i];//先将高度相同的一段加入队列 for(int i 0; i n; i ){int j i 1;while(j n a[i] a[j])j ;q.push({i, j - 1, a[i]});i j - 1;}//进行合并操作while(q.top().h 1){auto t q.top();q.pop();while(q.size() q.top().h t.h t.r 1 q.top().l)//如果堆非空并且现高度与相邻高度一致相邻即t.r 1 q.top().l) {t.r q.top().r;q.pop();}q.push({t.l, t.r, f(t.h)});if(t.h 1)res ;} cout res \n;return 0;
}
