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

缺乏、安全感 2023-09-29 00:16 28阅读 0赞

## 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.原题链接 ###

[砍竹子][Link 1]

## 2.解题思路 ##

注意观察式子  ⌊ ⌊ H 2 ⌋ + 1 ⌋ ⌊\\sqrt\{⌊\\frac H 2⌋+1\}⌋ ⌊⌊2H⌋\+1⌋，一边除以 `2` 同时还开方，显然竹子的高度会下降的非常快，即使  h i hi hi 取最大值 `1e18` ，经过验证最多也只需要砍  6 6 6 次即可让高度变为 `1`。 ![在这里插入图片描述][e02283e727564ab7bc461a75758d5eb4.png]  
所以我们显然可以暴力计算出每一颗竹子在变为 `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;
    }

[Link 1]: https://www.lanqiao.cn/problems/2117/learning/
[e02283e727564ab7bc461a75758d5eb4.png]: https://img-blog.csdnimg.cn/e02283e727564ab7bc461a75758d5eb4.png