在线段染色之类的题目中，这是一种很常见的做法。这里还可以用到线段树，可惜我还不会：-（

事实上，这也算最简单的离散化题目了。关键在于判断何时两条线段可以合并，何时拆散，合并后对多于线段的处理也很重要。值得高兴的是我qsort可以写的很熟练......

#include <cstdio>
#include <cstring>
#include <cstdlib>

typedef struct
{
    int b, e;
    char c;
} sect;

sect s[2001], r[20001];

int N, r_size, mx, ans_b, ans_e;

int cmp ( const void *a, const void *b )
{
    sect *A, *B;
    A = ( sect * ) a, B = ( sect * ) b ;
    return A->b > B->b ? 1 : -1;
}

int gt ( int a, int b )
{
    return a > b ? a : b;
}

void init ()
{
    int i;
    r_size = 0, mx = 0;
    for ( i = 0; i < N; i ++ )
    {
        scanf ( "%d %d %c ", &s[i].b, &s[i].e, &s[i].c );
        //printf ( "%d %d %c\n", s[i].b, s[i].e, s[i].c );
    }
    memset ( r, 0, sizeof ( r ) );
}

void dis ()
{
    int i, k;
    for ( i = 0; i < N; i ++ )
    {
        if ( s[i].c == 'w' )
        {
            r[r_size].b = s[i].b;
            r[r_size].e = s[i].e;
            r_size ++;
        }
        else if ( s[i].c == 'b' )
        {
            int t_size = r_size;
            //有四种情况需要考虑
            for ( k = 0; k < t_size; k ++ )
            {
                if ( s[i].b <= r[k].b && s[i].e >= r[k].b && s[i].e < r[k].e )
                {
                    r[k].b = s[i].e + 1;
                }
                else if ( s[i].e >= r[k].e && s[i].b <= r[k].e && s[i].b > r[k].b )
                {
                    r[k].e = s[i].b - 1;
                }
                else if ( s[i].b <= r[k].b && s[i].e >= r[k].e )
                {
                    r[k].b = r[k].e = -1;
                }
                else if ( s[i].b > r[k].b && s[i].e < r[k].e )
                {
                    r[r_size].e = r[k].e;
                    r[r_size].b = s[i].e + 1;
                    r[k].e = s[i].b - 1;
                    r_size ++;
                }
            }
        }
    }
    //pr ();
    qsort ( r, r_size, sizeof ( sect ), cmp );
    //pr ();
    int size, t_b = -1, t_e = -2;
    //临时保存开始和结尾为t_b与t_e，线性算法，和求最大子串和类似
    //设初始状态为-1 - (-2) + 1 = 0
    for ( i = 0; i < r_size; i ++ )
    {
        if ( r[i].b != -1 )
        {
            if ( r[i].b > t_e + 1 )
            {
                size = t_e - t_b + 1;
                if ( size > mx )
                {
                    mx = size;
                    ans_b = t_b;
                    ans_e = t_e;
                }
                t_b = r[i].b;
                t_e = r[i].e;
            }
            else
            {
                t_e = gt ( r[i].e, t_e );
            }
        }
    }
    size = t_e - t_b + 1;
    if ( size > mx )
    {
        mx = size;
        ans_b = t_b;
        ans_e = t_e;
    }
}

void print ()
{
    if ( mx == 0 )
    {
        printf ( "Oh, my god\n" );
    }
    else
    {
        printf ( "%d %d\n", ans_b, ans_e );
    }
}

int main ()
{
    //freopen ( "in.txt", "r", stdin );
    while ( scanf ( "%d ", &N ) != EOF )
    {
        init ();
        dis ();
        print ();
    }
    return 0;
}

评论