【洛谷 P8781】[蓝桥杯 2022 省 B] 修剪灌木 题解（模拟+差分）

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

题目描述

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

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

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

3

样例输出 #1

4
2
4

提示

对于 $30\%$ 的数据, $N\le 10$.

对于 $100\%$ 的数据, $1<N\le 10000$.

蓝桥杯 2022 省赛 B 组 D 题。

思路

在每个日期，首先模拟灌木的生长，然后模拟爱丽丝修剪灌木。在修剪灌木的过程中，使用差分数组来更新灌木的高度，这样可以快速地更新和查询灌木的高度。同时记录每棵灌木的最大高度，以便在最后输出。

在这个程序中，首先定义了一些常量和变量，包括灌木的数量 $n$，当前的日期 $day$，每棵灌木的高度数组 $ht$，每棵灌木的最大高度数组 $hmax$，以及差分数组 $diff$。

init 函数用于初始化这些数组。getHeight 函数用于计算给定日期的灌木高度。grow 函数模拟了每天灌木的生长过程，每天所有的灌木都会长高 $1$ 厘米。trim 函数模拟了每天傍晩爱丽丝修剪灌木的过程，修剪后的灌木高度会变为 $0$ 厘米，并且更新灌木的最大高度。

在 main 函数中，首先读入灌木的数量 $n$，然后初始化数组。然后模拟了爱丽丝修剪灌木的过程，直到每棵灌木都被修剪了两次。最后，输出每棵灌木的最大高度。

AC代码

#include <algorithm>
#include <cstring>
#include <iostream>
#define mp make_pair
#define AUTHOR "HEX9CF"
using namespace std;
using ll = long long;

const int N = 1e6 + 7;
const int INF = 0x3f3f3f3f;
const ll MOD = 1e9 + 7;

int n;
int day = 1;
int ht[N], hmax[N];
int diff[N];

void init(int x) {
	memset(ht, 0, sizeof(ht));
	memset(hmax, 0, sizeof(hmax));
	memset(diff, 0, sizeof(diff));
}

int getHeight(int x) {
	int h = 0;
	for (int i = 1; i <= x; i++) {
		ht[i] = ht[i - 1] + diff[i];
	}
	return ht[x];
}

// 灌木每天从早上到傍晩会长高 1 厘米
void grow() {
	diff[1]++;
	diff[n + 1]--;
	day++;
}

// 爱丽丝在每天傍晩会修剪一棵灌木
void trim(int x) {
	// 修剪前统计高度
	getHeight(x + 1);
	hmax[x] = max(hmax[x], ht[x]);
	// 修剪
	diff[x] -= ht[x];
	diff[x + 1] += ht[x];
	// cout << x << "\n";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	init(n);

	for (int i = 1; day <= 2 * n;) {
		for (; i < n; i++) {
			grow();
			trim(i);
		}
		for (; i > 1; i--) {
			grow();
			trim(i);
		}
	}

	getHeight(n);
	for (int i = 1; i <= n; i++) {
		cout << hmax[i] << "\n";
	}
	return 0;
}