[蓝桥杯 2022 省 B] 修剪灌木

题目链接

[蓝桥杯 2022 省 B] 修剪灌木

题目描述

爱丽丝要完成一项修剪灌木的工作。

有 $N$ 棵灌木整齐的从左到右排成一排。爱丽丝在每天傍晩会修剪一棵灌木，让灌木的高度变为 $0$ 厘米。爱丽丝修剪灌木的顺序是从最左侧的灌木开始，每天向右修剪一棵灌木。当修剪了最右侧的灌木后，她会调转方向，下一天开始向左修剪灌木。直到修剪了最左的灌木后再次调转方向。然后如此循环往复。

灌木每天从早上到傍晩会长高 $1$ 厘米, 而其余时间不会长高。在第一天的早晨, 所有灌木的高度都是 $0$ 厘米。爱丽丝想知道每棵灌木最高长到多高。

输入格式

一个正整数 $N$ ，含义如题面所述。

输出格式

输出 $N$ 行, 每行一个整数, 第行表示从左到右第 $i$ 棵树最高能长到多高。

输入输出样例

输入

3

输出

4
2
4

数据范围

• $1\le N\le 10000$

解法：模拟

对于第 $i$ 棵树的最大高度，实际就是 从第 $i$ 棵树离开，下一次到达第 $i$ 棵数的最大时间间隔 $t$，实际也就是最大的距离。

左边的距离为 $(i-1)\times 2$，右边的距离为 $(n-i)\times 2$。

那么第 $i$ 棵树的最大高度就是 $max\{(i-1)\times 2,(n-i)\times 2\}$。

时间复杂度：$O(n)$

C++代码：

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

void solve()
{
    int n;
    cin>>n;
    
    vector<int> ans(n + 1);
    for(int i = 1;i <= n;i++) ans[i] = max(i - 1, n - i) * 2;
    
    for(int i = 1;i <= n;i++) cout<<ans[i]<<'\n';
}

int main(){
    int t = 1;
    
    while(t--)
    {
        solve();
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

Java代码：

import java.util.*;
import java.io.*;

public class Main {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	public static void main(String[] args) throws Exception{
		int n = Integer.parseInt(in.readLine());
		
		int[] ans = new int[n + 5];
		for(int i = 1;i <= n;i++) {
			ans[i] = Math.max(i - 1, n - i) * 2;
		}
		
		for(int i = 1;i <= n;i++) {
			System.out.println(ans[i]);
		}
		
	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20