C11CAVE – spoj

Đề bài:

• http://vn.spoj.com/problems/C11CAVE/

Thuật toán:

• Chỉ cần duyệt từ 1 đến h rồi kiểm tra, bạn đọc code bên dưới sẽ hiểu.

Code:

• Pascal

    const           fi      = '';
                    fo      = '';
                    maxn    = 1000000;

    var
                    n , h   : longint;
                    m       : longint;
                    d , c   : array[ 0..maxn ] of longint;

    procedure   enter;
        var
                i           : longint;
                u , v       : longint;
        begin
                read( n , h );
                m := n div 2;
                for i := 1 to m do
                  begin
                    read( u , v );
                    inc( d[ u ] );
                    inc( c[ v ] );
                  end;
        end;

    procedure   prepair;
        var
                i           : longint;
        begin
                for i := 1 to h do
                  begin
                    d[ i ] := d[ i-1 ] + d[ i ];
                    c[ i ] := c[ i-1 ] + c[ i ];
                  end;
        end;


    procedure   solve;
        var
                res , num   : longint;
                i , tmp     : longint;
        begin
                res := n+1;
                num := 0;
                for i := 1 to h do
                  begin
                    tmp := d[ h ] - d[ i-1 ] + c[ h ] - c[ h-i ];
                    if res > tmp then
                      begin
                        res := tmp;
                        num := 1;
                      end
                    else
                      if res = tmp then inc( num );
                  end;
                writeln( res , ' ' , num );
        end;



    BEGIN

                assign( input , fi ); reset( input );
                assign( output , fo ); rewrite( output );

                enter;
                prepair;
                solve;

                close( input ); close( output );

    END.