题意是询问一个动态序列的最小值和最大值。
可以用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); } }