C11CAVE – spoj

Đề bài:

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:

    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.
Khuyên dùng

 

Speak Your Mind

*