'priority_queue'에 해당되는 글 1건

  1. 2008/02/17 귀차니스트 Ecological Bin Packing
◀ 이전페이지 1 다음페이지 ▶

Ecological Bin Packing

Algorithm/Acm 2008/02/17 08:30 귀차니스트
  1. 문제링크 : http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=38
  2.  의   견   : 나올 수 있는 경우의 수는 3! 개 입니다. 즉, 경우의 수가 적으므로 6가지 경우에 대한 측정값들을 수동으로 계산하여 출력할 수 있습니다. 하지만, 일반적으로 계산을 해보고자 하는 마음으로 priority_queue와 string을 짝으로 조합하여 구현을 했습니다.
  3. 소스
    103.cpp (Language : cpp)
    1. #include <iostream>
    2. #include <queue>
    3. #include <string>
    5. struct SortNode {
    6.     int Total;
    7.     std::string OutputStr;
    8. };
    10. bool operator < ( const SortNode &Left, const SortNode &Right )
    11. {
    12.     size_t LeftLength = Left.OutputStr.length();
    13.     size_t RightLength = Right.OutputStr.length();
    15.     if( ( Left.Total == Right.Total ) && ( LeftLength == RightLength ) )    {
    16.         for( int i = 0; i < 3; i++ )    {
    18.             char LeftChar = Left.OutputStr[ i ];
    19.             char RightChar = Right.OutputStr[ i ];
    21.             if( LeftChar == RightChar )
    22.                 continue;
    23.             else if( LeftChar > RightChar )
    24.                 return true;
    25.             else
    26.                 return false;
    27.         }
    28.     }
    30.     return ( Left.Total > Right.Total );
    31. }
    33. int main( int argc, char **argv )
    34. {
    35.     unsigned int Bottle[ 9 ] = { 0, };
    37.     while( std::cin >> Bottle[ 0 ] >> Bottle[ 1 ] >> Bottle[ 2 ] >> Bottle[ 3 ] >> Bottle[ 4 ] >> Bottle[ 5 ] >> Bottle[ 6 ] >> Bottle[ 7 ] >> Bottle[ 8 ] )    {
    38.         std::priority_queue< SortNode > BackTracking;
    40.         SortNode Temp;
    41.         Temp.Total = 0;
    42.         BackTracking.push( Temp );
    44.         while( true )   {
    46.             SortNode ProcessNode = BackTracking.top();
    47.             BackTracking.pop();
    49.             size_t ProcessStrLength = ProcessNode.OutputStr.length();
    51.             if( ProcessStrLength == 3 ) {
    52.                 std::cout << ProcessNode.OutputStr << " " << ProcessNode.Total << std::endl;
    53.                 break;
    54.             }
    56.             ProcessStrLength *= 3;
    58.             if( ProcessNode.OutputStr.find( "C" ) == UINT_MAX ) {
    59.                 SortNode CNode( ProcessNode );
    61.                 CNode.Total += ( Bottle[ ProcessStrLength ] + Bottle[ ProcessStrLength + 1 ] );
    62.                 CNode.OutputStr += "C";
    64.                 BackTracking.push( CNode );
    65.             }
    67.             if( ProcessNode.OutputStr.find( "G" ) == UINT_MAX ) {
    68.                 SortNode GNode( ProcessNode );
    70.                 GNode.Total += ( Bottle[ ProcessStrLength ] + Bottle[ ProcessStrLength + 2 ] );
    71.                 GNode.OutputStr += "G";
    73.                 BackTracking.push( GNode );
    74.             }
    76.             if( ProcessNode.OutputStr.find( "B" ) == UINT_MAX ) {
    77.                 SortNode BNode( ProcessNode );
    79.                 BNode.Total += ( Bottle[ ProcessStrLength + 1 ] + Bottle[ ProcessStrLength + 2 ] );
    80.                 BNode.OutputStr += "B";
    82.                 BackTracking.push( BNode );
    83.             }
    84.         }
    85.     }
    87.     return 0;
    88. }



크리에이티브 커먼즈 라이센스
Creative Commons License

"Algorithm / Acm" 분류의 다른 글

The Blocks Problem (0)2008/02/17
3n+1 Problem (0)2008/02/17
The Skyline Problem (2)2008/02/17
Maximum Sum (0)2008/02/17
LCD Display (3)2008/02/17
2008/02/17 08:30 2008/02/17 08:30
TAG , , , ,
받은 트랙백이 없고, 댓글이 없습니다.

댓글을 달아 주세요

◀ 이전페이지 1 다음페이지 ▶