Skip to main content

一维前缀和(刷出一道墙)

tip

在一面很长的墙壁上,工人们用不同的油漆去刷墙,然而可能有些地方刷过以后觉得不好看,他们会重新刷一下。有些部分因为重复刷了很多次覆盖了很多层油漆,小诺很好奇那些地方被刷过多少种颜色的油漆。

输入描述:

若干行输入,每行两个数字B[i],E[i](0<=B[i]<=E[i]<=200000)表示这次刷的墙壁是哪一段
(假设每次刷的时候油漆颜色都和之前的不同),以0 0结束
又若干行输入,每行两个数字begin[i],end[i](0<=begin[i]<=end[i]<=200000)表示小诺询问的段,
以0 0结束

输出描述:

对于每个小诺的询问输出(end[i]-begin[i]+1)行,表示对应询问段的每个点被多少种颜色的油漆覆盖过。

参考代码

#include <bits/stdc++.h>

using namespace std;

int main()
{
vector<int> colors(200001, 0);

int B, E;
while (scanf("%d %d", &B, &E))
{
if (B == 0 && E == 0)
{
break;
}
colors[B]++; // 刷墙起点标记
colors[E + 1]--; // 刷墙终点标记
}

// 计算前缀和
for (int i = 1; i < colors.size(); i++)
{
colors[i] += colors[i - 1];
}

int begin, end;
while (scanf("%d %d", &begin, &end))
{
if (begin == 0 && end == 0)
{
break;
}
for (int i = begin; i <= end; i++)
{
printf("%d\n", colors[i]);
}
}

return 0;
}

题解

使用前缀和思想简化时间复杂度,设计前缀和数组,使输出的数组中元素的值代表其对应节点被刷的次数。

首先初始化前缀和数组,使每一个元素等于为0。

该题的巧妙之处就在于:对于每一个输入的索引B与E,B作为开始刷的节点索引令前缀和数组中对应元素的值+1+1,E+1作为刷墙结束的下一个节点的索引令对应的值1-1。这样在所有输入结束后的计算前缀和阶段,在每一个值为[1,1)[1, -1)的索引区间中的元素值都会加1,而对于某次刷漆终点E的下一个索引为E+1的元素值由于1-1而抵消影响(自身值为1-1加上之前元素所累积的1而归零),此时数组中元素的值才代表其对应节点被刷的次数。

关于超时,可以在函数中加入以下代码消除流操作的缓冲区,并使用"\n"代替endl。

ios::sync_with_stdio(false);