bills;intsum=0;for(inti=0;i

Hoax or what

系统 1665 0

Hoax or what

题意是询问一个动态序列的最小值和最大值。

可以用multiset来实现。

      #include <stdio.h>
      
        

#include 
      
      <
      
        set
      
      >


      
        using
      
      
        namespace
      
      
         std;




      
      
        int
      
      
         main() {

    freopen(
      
      
        "
      
      
        h.in
      
      
        "
      
      , 
      
        "
      
      
        r
      
      
        "
      
      
        , stdin);

    freopen(
      
      
        "
      
      
        h.ans
      
      
        "
      
      , 
      
        "
      
      
        w
      
      
        "
      
      
        , stdout);

    
      
      
        int
      
      
         n;

    
      
      
        while
      
       (scanf(
      
        "
      
      
        %d
      
      
        "
      
      , &n) &&
      
         n) {

        multiset
      
      <
      
        int
      
      >
      
         bills;

        
      
      
        int
      
       sum = 
      
        0
      
      
        ;

        
      
      
        for
      
       (
      
        int
      
       i = 
      
        0
      
      ; i < n; i++
      
        ) {

            
      
      
        int
      
      
         cnt;

            scanf(
      
      
        "
      
      
        %d
      
      
        "
      
      , &
      
        cnt);

            
      
      
        for
      
       (
      
        int
      
       j = 
      
        0
      
      ; j < cnt; j++
      
        ) {

                
      
      
        int
      
      
         t;

                scanf(
      
      
        "
      
      
        %d
      
      
        "
      
      , &
      
        t);

                bills.insert(t);

            }



            sum 
      
      += (*bills.rbegin() - *
      
        bills.begin());



            bills.erase(bills.begin());

            bills.erase(
      
      --bills.rbegin().
      
        base
      
      
        ());

        }

        printf(
      
      
        "
      
      
        %d\n
      
      
        "
      
      
        , sum);

    }

}
      
    

这里给出一个最小堆的做法,通过维护一个最小堆,一个最大堆,当push元素时,将这两个元素连接到一起。当pop最大或者最小的元素时,对应删除另一个堆中对应的元素。

      #include <stdio.h>
      
        

#include 
      
      <algorithm>
      
        

#include 
      
      <iostream> 


      
        using
      
      
        namespace
      
      
         std;




      
      
        const
      
      
        int
      
       MAXN = 1e6 + 
      
        5
      
      
        ;


      
      
        const
      
      
        int
      
       INF =
      
         1e9;




      
      
        int
      
      
         min_heap[MAXN], max_heap[MAXN];


      
      
        int
      
      
         min_heap_no[MAXN], max_heap_no[MAXN];


      
      
        int
      
      
         min_heap_no_rev[MAXN], max_heap_no_rev[MAXN];




      
      
        class
      
      
         MinHeap {


      
      
        protected
      
      
        :

    
      
      
        int
      
       count, *
      
        heap_;


      
      
        public
      
      
        :

    MinHeap() {}

    MinHeap(
      
      
        int
      
       *heap) : heap_(heap), count(
      
        0
      
      
        ) {}

    
      
      
        void
      
       push(
      
        int
      
      
         x) {

        
      
      ++
      
        count;

        heap_[count] 
      
      =
      
         x;

        up(count);

    }

    
      
      
        int
      
      
         top() {

        
      
      
        return
      
       heap_[
      
        1
      
      
        ];

    }

    
      
      
        void
      
      
         pop() {

        my_swap(
      
      
        1
      
      , count--
      
        );

        heapfy(
      
      
        1
      
      
        );

    }

    
      
      
        /*
      
      
        {{{ del(int i)
      
      
        */
      
      
        void
      
       del(
      
        int
      
      
         i) {

        heap_[i] 
      
      = -
      
        INF; up(i);

        pop();

    }

    
      
      
        /*
      
      
        }}}
      
      
        */
      
      
        virtual
      
      
        void
      
       my_swap(
      
        int
      
       i, 
      
        int
      
      
         j) {

        swap(heap_[i], heap_[j]);

    }

    
      
      
        /*
      
      
        {{{ heapfy(int i) 
      
      
        */
      
      
        void
      
       heapfy(
      
        int
      
      
         i) {

        
      
      
        while
      
       (i <=
      
         count) {

            
      
      
        int
      
       smallest =
      
         i;

            
      
      
        if
      
       (
      
        2
      
       * i <= count && heap_[
      
        2
      
       * i] <
      
         heap_[smallest]) {

                smallest 
      
      = 
      
        2
      
       *
      
         i;

            }

            
      
      
        if
      
       (
      
        2
      
       * i + 
      
        1
      
       <= count && heap_[
      
        2
      
       * i + 
      
        1
      
      ] <
      
         heap_[smallest]) {

                smallest 
      
      = 
      
        2
      
       * i + 
      
        1
      
      
        ;

            }

            
      
      
        if
      
       (i !=
      
         smallest) {

                my_swap(i, smallest);

                i 
      
      =
      
         smallest;

            } 
      
      
        else
      
      
         {

                
      
      
        break
      
      
        ;

            }

        }

    }

    
      
      
        /*
      
      
        }}}
      
      
        */
      
      
        /*
      
      
        {{{ up(int i) 
      
      
        */
      
      
        void
      
       up(
      
        int
      
      
         i) {

        
      
      
        while
      
       (i > 
      
        1
      
      
        ) {

            
      
      
        if
      
       (heap_[i] < heap_[i / 
      
        2
      
      
        ]) {

                my_swap(i, i 
      
      / 
      
        2
      
      
        );

                i 
      
      /= 
      
        2
      
      
        ;

            } 
      
      
        else
      
      
         {

                
      
      
        break
      
      
        ;

            } 

        }

    }

    
      
      
        /*
      
      
        }}}
      
      
        */
      
      
        

};




      
      
        class
      
       MinHeapWithMap : 
      
        public
      
      
         MinHeap {


      
      
        private
      
      
        :

    
      
      
        int
      
       id, *no_, *
      
        no_rev_;


      
      
        public
      
      
        :

    MinHeapWithMap() {}

    MinHeapWithMap(
      
      
        int
      
       *heap, 
      
        int
      
       *no, 
      
        int
      
       *no_rev) : MinHeap(heap), no_(no), no_rev_(no_rev), id(
      
        0
      
      
        ) {}

    
      
      
        void
      
       push(
      
        int
      
      
         x) {

        no_[count 
      
      + 
      
        1
      
      ] =
      
         id;

        no_rev_[no_[count 
      
      + 
      
        1
      
      ]] = count + 
      
        1
      
      
        ;

        id
      
      ++
      
        ;

        MinHeap::push(x);

    }

    
      
      
        virtual
      
      
        void
      
       my_swap(
      
        int
      
       i, 
      
        int
      
      
         j) {

        MinHeap::my_swap(i, j);

        swap(no_[i], no_[j]);

        no_rev_[no_[i]] 
      
      =
      
         i;

        no_rev_[no_[j]] 
      
      =
      
         j;

    }

    
      
      
        int
      
      
         top_no() {

        
      
      
        return
      
       no_[
      
        1
      
      
        ];

    }

    
      
      
        int
      
       no_rev(
      
        int
      
      
         i) {

        
      
      
        return
      
      
         no_rev_[i]; 

    }

};




      
      
        class
      
      
         Solution {


      
      
        private
      
      
        :

    MinHeapWithMap minHeap_, maxHeap_;


      
      
        public
      
      
        :

    Solution() {

        minHeap_ 
      
      =
      
         MinHeapWithMap(min_heap, min_heap_no, min_heap_no_rev);

        maxHeap_ 
      
      =
      
         MinHeapWithMap(max_heap, max_heap_no, max_heap_no_rev);

    }

    
      
      
        void
      
       push(
      
        int
      
      
         x) {

        minHeap_.push(x);

        maxHeap_.push(
      
      -
      
        x);

    }

    
      
      
        int
      
      
         getMaxMinDiff() {

        
      
      
        int
      
       res = -maxHeap_.top() -
      
         minHeap_.top();

        minHeap_.del(minHeap_.no_rev(maxHeap_.top_no()));

        maxHeap_.del(maxHeap_.no_rev(minHeap_.top_no()));

        minHeap_.pop();

        maxHeap_.pop();

        
      
      
        return
      
      
         res;

    }

};




      
      
        int
      
      
         main() {

    freopen(
      
      
        "
      
      
        h.in
      
      
        "
      
      , 
      
        "
      
      
        r
      
      
        "
      
      
        , stdin);

    freopen(
      
      
        "
      
      
        h.out
      
      
        "
      
      , 
      
        "
      
      
        w
      
      
        "
      
      
        , stdout);

    
      
      
        int
      
      
         n;

    
      
      
        while
      
       ( scanf(
      
        "
      
      
        %d
      
      
        "
      
      , &
      
        n), n) {

        Solution s;

        
      
      
        int
      
       sum = 
      
        0
      
      
        ;

        
      
      
        for
      
       (
      
        int
      
       i = 
      
        0
      
      ; i < n; i++
      
        ) {

            
      
      
        int
      
      
         k;

            scanf(
      
      
        "
      
      
        %d
      
      
        "
      
      , &
      
        k);

            
      
      
        for
      
       (
      
        int
      
       j = 
      
        0
      
      ; j < k; j++
      
        ) {

                
      
      
        int
      
      
         t;

                scanf(
      
      
        "
      
      
        %d
      
      
        "
      
      , &
      
        t);

                s.push(t);

            }

            sum 
      
      +=
      
         s.getMaxMinDiff();

        }



        printf(
      
      
        "
      
      
        %d\n
      
      
        "
      
      
        , sum);

    }

}
      
    

 

Hoax or what


更多文章、技术交流、商务合作、联系博主

微信扫码或搜索:z360901061

微信扫一扫加我为好友

QQ号联系: 360901061

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请用微信扫描下面二维码支持博主2元、5元、10元、20元等您想捐的金额吧,狠狠点击下面给点支持吧,站长非常感激您!手机微信长按不能支付解决办法:请将微信支付二维码保存到相册,切换到微信,然后点击微信右上角扫一扫功能,选择支付二维码完成支付。

【本文对您有帮助就好】

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请用微信扫描上面二维码支持博主2元、5元、10元、自定义金额等您想捐的金额吧,站长会非常 感谢您的哦!!!

发表我的评论
最新评论 总共0条评论