首页 - 新闻 - HDU-1556：给球上色（前缀和）

HDU-1556：给球上色（前缀和）

2023-10-08 03:27

-->

给球涂色

时间限制：9000/3000 MS（Java/其他）

内存限制：32768/32768 K（Java/其他）

提交总数：26275

已接受提交：12734

问题描述

N 个气球排成一排，从左到右编号为 1、2、3...N。每次给出2个整数a b（a <= b），乐乐就会骑上他的“小飞鸽”牌电动车，从气球a开始到气球b依次给每个气球涂色。但N次之后，乐乐已经忘记了第I个气球被画了多少次了。你能帮他数一下每个气球被画了多少次吗？

输入

每个测试实例的第一行包含一个整数N，（N <= 100000）。接下来的N行，每行包含2个整数a b (1 <= a <= b <= N)。
当N=0时，输入结束。

输出

每个测试实例输出一行，包含N个整数。第 I 个数字表示第 I 个气球已被绘制的总次数。

样本输入

1 1

2 2

3 3

1 1

1 2

1 3

样本输出

1 1 1

3 2 1

想法：一开始涂颜色的次数是一样的，都是0，每次涂颜色都给区间内的所有值+1。最坏的 O(n²) 暴力是不可能的，这里引入 O(n) 前缀和方法，代码量也很小。其实我们之前在POJ3263题中已经介绍过前缀和的思想，即将一个区间的操作转换为左右端点的操作。不过，上次我是在胡说八道，没有自己画过图的同学应该只是一知半解。这次我就借这个问题来复习一下。

方法如下：打开两个数组c和d。我用c数组来表示要输出的数组，即气球实际被绘制的次数。显然，一开始它们都是0。 d 数组用于“一旦给出一个区间，并且需要我们执行着色操作，我们就在 d 上标记其左右端点”。这里我们首先给出c和d之间的递归关系。请通过下图来了解我们如何利用标记的d数组来查找所需的c数组。

举个例子吧。比如一开始c和d都是0，我们先画1~3，那么就需要d[1]++,d[3+1]--；表示第一个下标应该比第0个下标的c值少1（实际上多了一个d[1]，刚刚修改了一次，所以是1），第4个下标应该比第0个下标的c值少1 c 第三个下标的值（同上）。

如果这时候输入还没有完成，我们就不能这么早要c了。在此基础上，输入另一组，绘制2~3。显然，这样完成后，我们要输出的c就是：1,2,2，试试看行不行。

我希望这个图文并茂的解释能够澄清前缀和的一般含义。这样有兴趣的同学就可以回去重做POJ3263了。基本思想是一样的，只是区间的开闭不同。

这段代码没有注释，因为上面已经解释得差不多了。

#包括
#包括
#包括
#包括
使用命名空间 std； int n,a,b;
int d[],c[]; int main()
{
while(~scanf("%d",&n)&&n)
{
memset(d,,sizeof(d));
memset(c,,sizeof(c));
for(int i=;i<=n;i++)
{
scanf("%d%d",&a,&b);
if(a>b) 交换(a,b);
d[a]++;
d[b+]--;
}
for(int i=;i<=n;i++)
c[i]=c[i-]+d[i],printf("%d%c",c[i],"\n"[i==n]);
}
返回；
} -->