Time Limit: 9000/3000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 30619
Accepted Submission(s): 14830
Problem DescriptionN个气球排成一排，从左到右依次编号为1,2,3…N.每次给定2个整数a b(a <= b),lele便为骑上他的“小飞鸽"牌电动车从气球a开始到气球b依次给每个气球涂一次颜色。但是N次以后lele已经忘记了第I个气球已经涂过几次颜色了，你能帮他算出每个气球被涂过几次颜色吗？
Input每个测试实例第一行为一个整数N,(N <= 100000).接下来的N行，每行包括2个整数a b(1 <= a <= b <= N)。
当N = 0，输入结束。
Output每个测试实例输出一行，包括N个整数，第I个数代表第I个气球总共被涂色的次数。
Sample Input3
1 1
2 2
3 3
3
1 1
1 2
1 3
0
Sample Output
1 1 1
3 2 1
理解：
对于这道题 开始很容易想到用暴力解法去做 就是给什么数字 就给它所对应的下标上加一 清楚明了 但对这道题来说N方的复杂度是超时的 所以我们需要想一些其他的方法来解决这个问题 有一个很巧妙的思路 就是在取区间值的时候 我们给其区间对应的start加一 end减一 循环直到所有的值都已经取入数组 然后进行读出 这是这道题最精髓的一步 就是从数组左边向右边读 然后
if(k!=1)
a[k]+=a[k-1];这样看可能有点不好理解 我们可以这样想 假如区间为[1,3] 我们给 1 位置加一 4 位置减一 这样的话前三个位置都是一 但如果这个时候有一个区间[1,2] 1 位置再加一 成了二 而 3 位置减一相当于前面一二位置仍然加一 而三位置成了减一 因为这个位置本来就不需要加一
以下是第一次超时的做法：
#include<stdio.h>
#include<stdlib.h>
main()
{
int i,j,m,n,k,tmp;
while(~scanf("%d",&k))
{
if(k==0) exit(1);
int a[100100]={0};
for(i=0;i<k;i++)
{
scanf("%d %d",&m,&n);
for(j=m;j<=n;j++)
a[j-1]++;
}
for(j=0;j<k-1;j++)
printf("%d ",a[j]);
printf("%d\n",a[j]);
}
}这个是AC代码：
#include<stdio.h>
#include<stdlib.h>
int main()
{
int m,n,i,j,k;
while(~scanf("%d",&m))
{
if(m==0) exit(1);
int a[100001]={0};
for(n=0; n<m; n++)
{
scanf("%d %d",&i,&j);
a[i]++;
a[j+1]--;
}
for(k=1; k<=m; k++)
{
if(k!=1)
a[k]+=a[k-1];
printf("%d",a[k]);
if(k<m)
printf(" ");
}
printf("\n");
}
}ps：看了网上的题解 这道题标准解法是用线段树来做的 过一阵再写一个线段树的代码 这个代码就当是扩展思维了