题解：AtCoder Beginner Contest AT_abc379_d ABC379D Home Garden

题目大意

有 $10^{100}$ 个花盆，刚开始时没有花。

现在将要按顺序进行 $Q$ 次操作。

对于每一次，你要执行的是以下三种中的第 $op$ 种：

1. 找一个空花盆，栽一朵高度为零的花，注意不需要任何时间。
2. 让时间过去 $T$ 天，所有活着的花长高 $T$ 厘米。
3. 移除所有高度大于等于 $H$ 的花，注意不需要任何时间，移除的花不会继续生长。请输出你移走了多少盆花。

思路

• 题目中给出的大数字 $10^{100}$ 是为了告诉你，不用担心花盆不够。
• 操作一可以在你种的所有花后面种植新的花。
• 操作二是不是有点像差分算法？事实上，这确实可以用差分维护，但它本质上就是个后缀和，这是基于上面那点（关于操作一如何实现的那点）的。
• 操作三，基于操作二的维护。说它像后缀和，我们就计算后缀和，算完后把满足要求的统计出来即可。注意一个细节：被移除的花一定要标记一下，计算后缀和以及统计答案时也要注意。

代码实现

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

int q, cnt, vis[200010]; // cnt 用来记录已经使用了多少个花盆（被移除的也算），vis 用来记录是否被移除
long long d[200010]; // d 是差分数组，即变化

int main()
{
    cin >> q;
    while (q--)
    {
    	int op;
    	cin >> op;
    	if (op == 1)
    		cnt++; // 种一朵花
    	else if (op == 2)
    	{
    		int t;
    		cin >> t;
    		d[cnt] += t; // 变化：集体加 T
		}
		else
		{
			int h;
			cin >> h;
			int ans = 0;
			long long s = 0;
			for (int i = cnt; i >= 1; i--) // 倒着求后缀和
			{
				if (vis[i]) // 这盆花被移除，跳过
					continue;
				s += d[i]; // 加上变化
				if (s >= h) // 如果可以移走
				{
					ans++;
					vis[i] = 1; // 标记
				}
			}
			cout << ans << endl;
		}
	}
    return 0;
}

Submission #59587645: Accepted

关于代码时间复杂度

时间复杂度看似 $O(Q^2)$，但是在实现上可以避免超时。

我们最外面的一重循环是不能改变的，但是在计算后缀和的循环里有一些小细节。

观察到，循环会在每一个操作三中进行，循环的次数为操作一的个数。操作一的个数与操作三的个数之和小于 $Q$。

总之，以上代码虽然理论时间复杂度较高，但是在代码实现时并不会超时。