1.砍竹子

1.题目描述

这天小明在砍竹子他面前有 $n$ 棵竹子排成一排一开始第 $i$棵竹子的高度为 $hi$。

他觉得一棵一棵砍太慢了决定使用魔法来砍竹子。

魔法可以对连续的一段相同高度的竹子使用假设这一段竹子的高度为 $H$
那么使用一次魔法可以把这一段竹子的高度都变为 $\lfloor \sqrt{\lfloor \frac{H}{2}\rfloor +1}\rfloor$
其中 $\lfloor x\rfloor$ 表示对 $x$ 向下取整。

小明想知道他最少使用多少次魔法可以让所有的竹子的高度都变为 1。

2.输入格式

第一行为一个正整数 $n$表示竹子的棵数。

第二行共 $n$ 个空格分开的正整数 $hi$表示每棵竹子的高度。

3.输出格式

一个整数表示答案。

4.数据范围

$1\le n\le 2\times 10^5,1\le hi\le 10^{18}$。

5.原题链接

砍竹子

2.解题思路

注意观察式子 $\lfloor \sqrt{\lfloor \frac{H}{2}\rfloor +1}\rfloor$一边除以 2 同时还开方显然竹子的高度会下降的非常快即使 $hi$ 取最大值 1e18 经过验证最多也只需要砍 $6$ 次即可让高度变为 1。
所以我们显然可以暴力计算出每一颗竹子在变为 1 的过程中间值是多少同时计算出暴力砍掉所有竹子总共需要砍多少次。
出于贪心地考虑当某两颗相邻的竹子存在高度相同的情况时我们显然可以将它们一起砍这样我们的次数就需要减去1答案显然会更优。所以我们接下来暴力枚举相邻的竹子每存在一对相同值则让次数减1最终得到答案。
时间复杂度$O(nlog{h}_i)。$

Ac_code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> PII;
#define pb(s) push_back(s);
#define SZ(s) ((int)s.size());
#define ms(s,x) memset(s, x, sizeof(s))
#define all(s) s.begin(),s.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int N = 200010;

int n;
std::vector<LL> e[N];
void solve()
{
	cin >> n;
	std::vector<LL> a(n);
	for (auto& x : a) cin >> x;
	LL ans = 0;
	for (int i = 0; i < n; ++i) {
		LL v = a[i];
		while (v > 1) {
			e[i].push_back(v);
			v = sqrtl(v / 2 + 1);
			ans++;
		}
	}
	for (int i = 1; i < n; ++i) {
		for (LL x : e[i - 1]) {
			for (LL v : e[i]) {
				if (x == v) ans--;
			}
		}
	}
	cout << ans << '\n';
}
int main()
{
	ios_base :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t = 1;
	while (t--)
	{
		solve();
	}
	return 0;
}