第十三届蓝桥杯C++B组省赛J题——砍竹子（AC）

1.砍竹子 1.题目描述

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

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

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

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

2.输入格式

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

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

3.输出格式

一个整数表示答案。

4.数据范围

1 ≤ n ≤ 2 × 1 0 5 , 1 ≤ h i ≤ 1 0 18 1≤n≤2×10^5,1≤hi≤10^{18} 1≤n≤2×105,1≤hi≤1018。

5.原题链接

砍竹子

2.解题思路

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

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; }