AcWing 4409. 砍竹子 - AcWing

题目描述

题目分析 

注：sqrtl的范围为long double，比sqrt更加精确

使用优先队列维护一段区间，如果连续一段相同就合并为一个区间，从大到小去枚举，每次先取出最大的一段，双关键字排序，第一关键字是v，第二关键字是区间的左端点，先把堆顶元素取出，取完之后，能合并的合并在一起，合并完之后统一做一次操作即可

#include<bits/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_queue<node> 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;
}