在线段染色之类的题目中，这是一种很常见的做法。这里还可以用到线段树，可惜我还不会：-（ 事实上，这也算最简单的离散化题目了。关键在于判断何时两条线段可以合并，何时拆散，合并后对多于线段的处理也很重要。值得高兴的是我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;} 2265613 2007-03-13 15:16:34 Accepted 2301 C++ 00:00.02 712K Crux.D    

评论