HDOJ 1556( 绝对原创且通俗的讲解 )

题目很简单，普通的思路也很简单，不过这种思路一定是超时的！这道题，卡了一个多月，尝试在网上找一些题解，但是代码老长了，说是用到了线段树之类的高级的东西，确实还不懂。最后发现了一种很简单的代码，一开始真心看不懂，钻研许久，终于看懂了，我的这一篇博文应该是第一篇比较详细地解释这个问题的，下面是我的思考！

在这种高效的实现中，用到了累加的思想！他的做法就是在所给的闭区间的起点，用一个数组表示再以该起点以及之后的值都要自增一次。举个例子，给一个区间[ a, b ]，则使用一个数组sum[a]++;( 起始值都为零 )，说明a以及之后的总值都要加一，但是b之后的值不用加一，所以sum[b+1]--表示b以后的值自减( 因为前面的sum[a]++ 已经使b后面的值自增了，所以在这里要减掉 )。如果你到这里还不懂的话，请注意我前面提到的一个词——“累加”。我们所要的sum[]数组，就是记录当前点以及后面的点被加了多少次( 右端点多加的也是通过sum[]数组来减去多加的！ )。通过这种做法，我们可以很简单高效的解决这一道问题而不用用到线段树这种高级的数据结构！不得不感叹一句人类真是伟大！

说了这么多，不知你懂了没？下面是代码：

#include <iostream>
#include <cstdio>
#define N 100001

using namespace std;

int main()
{
    int n;
    while( scanf( "%d", &n ) && n != 0 )
    {
        int sum[N] = {0};
        int l, r;
        int ans = 0;

        for( int i = 0; i < n; i++ )
        {
            scanf( "%d%d", &l, &r );
            sum[l]++;
            sum[r+1]--;
        }
        for( int i = 1; i <= n; i++ )
        {
            ans += sum[i];
            printf( "%d", ans );
            if( i != n )
            {
                putchar( ‘ ‘ );
            }
        }
        putchar( ‘\n‘ );
    }
    return 0;
}

HDOJ 1556( 绝对原创且通俗的讲解 ),布布扣,bubuko.com

HDOJ 1556( 绝对原创且通俗的讲解 )

原文：http://blog.csdn.net/u011564456/article/details/22963033