HDU5014Number Sequence(貪心)

題目鏈接

題目大意：
給出n，然后給出一個(gè)數(shù)字串，長度為n + 1， 范圍在[0, n - 1].然后要求你找出另外一個(gè)序列B，滿足上述的要求，而且使得t = A0^B0 + Ai + 1 ^ Bi + 1 + ... + An ^ Bn 最大。

解題思路：
對(duì)于一個(gè)數(shù)字進(jìn)行異或，要求結(jié)果最大的話，那么取這個(gè)數(shù)字的二進(jìn)制互補(bǔ)數(shù)字是最好的情況，而且能夠發(fā)現(xiàn)每次找到一個(gè)數(shù)字和相應(yīng)的互補(bǔ)的數(shù)字都會(huì)是一段區(qū)間。就這樣一段一段區(qū)間的去尋找每一個(gè)點(diǎn)相應(yīng)的最好的匹配點(diǎn)。

代碼：

      
        
          #
          
            include
          
           <cstdio>
        
        
          #
          
            include
          
           <cstring>
        
        
          typedef
        
        
          long
        
        
          long
        
         ll;

        
          const
        
        
          int
        
         N = 
        
          1e5
        
         + 
        
          5
        
        ;

        
          const
        
        
          int
        
         M = 
        
          20
        
        ;


        
          int
        
         num[N];

        
          int
        
         Map[N];

        
          int
        
         n;
ll t[M];


        
          void
        
         init () {

    t[
        
          0
        
        ] = 
        
          1
        
        ;
    
        
          for
        
         (
        
          int
        
         i = 
        
          1
        
        ; i <= M; i++)
        t[i] = t[i - 
        
          1
        
        ] * 
        
          2
        
        ;
}


        
          int
        
         main () {

    init();
    
        
          while
        
         (
        
          scanf
        
         (
        
          "%d"
        
        , &n) == 
        
          1
        
        ) {

        
        
          for
        
         (
        
          int
        
         i = 
        
          0
        
        ; i <= n; i++)
            
        
          scanf
        
         (
        
          "%d"
        
        , &num[i]);

        
        
          int
        
         rear = n;
        
        
          int
        
         front;
        ll ans = 
        
          0
        
        ;

        
          // printf ("%lld\n", t[M - 1]);
        
        
          while
        
         (rear >= 
        
          0
        
        ) {

            
        
          for
        
         (
        
          int
        
         i = 
        
          0
        
        ; i < M; i++)
                
        
          if
        
         (t[i] > rear) {
                    front = t[i] - rear - 
        
          1
        
        ;
                    
        
          break
        
        ;        
                }

            
        
          for
        
         (
        
          int
        
         i = 
        
          0
        
        ; i < (rear - front + 
        
          1
        
        ) / 
        
          2
        
        ; i++) {

                Map[rear - i] = front + i;
                Map[front + i] = rear - i;
            }

            
        
          if
        
         (rear == front)
                Map[rear] = front;
            rear = front - 
        
          1
        
        ;
        }

        
        
          for
        
         (
        
          int
        
         i = 
        
          0
        
        ; i <= n; i++)
            ans += num[i] ^ Map[num[i]];
        
        
          printf
        
         (
        
          "%lld\n"
        
        , ans);
        
        
          for
        
         (
        
          int
        
         i = 
        
          0
        
        ; i < n; i++)
            
        
          printf
        
        (
        
          "%d "
        
        , Map[num[i]]);
        
        
          printf
        
         (
        
          "%d\n"
        
        , Map[num[n]]);
    }
    
        
          return
        
        
          0
        
        ;
}