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