/*
解题思路：每次只求解一开始的第一个数字，让第一个数字加一，最后的一个数字的后面一个数减一。我们可以想想，最后加的时候，就是加上前面一个数出现的次数和自己本身出现的次数。
解题人：lingnichong
解题时间：2014-10-25 10:30:46
解题体会：由于测试区间很大，所以此题很容易超时
*/

Color the ball

3
1 1
2 2
3 3
3
1 1
1 2
1 3
0

1 1 1
3 2 1

#include<stdio.h>
#include<string.h>
#define MAXN 100000+10
int arr[MAXN];
int main()
{
	int N,i,j;
	int a,b,t,m;
	while(scanf("%d",&N),N)
	{
		m=0;
		memset(arr,0,sizeof(arr));
		for(i=0;i<N;i++)
		{
		    scanf("%d%d",&a,&b);
		    arr[a]++,arr[b+1]--;
		}
		for(i=1;i<N;i++)
		{
			m+=arr[i];
			printf("%d ",m);
		}
		printf("%d\n",m+arr[N]);
	}
	return 0;
}

HDU 1556 Color the ball【算法的优化】

原文：http://blog.csdn.net/qq_16767427/article/details/40454233