題意是詢問(wèn)一個(gè)動(dòng)態(tài)序列的最小值和最大值。
可以用multiset來(lái)實(shí)現(xiàn)。
#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);
}
}
這里給出一個(gè)最小堆的做法，通過(guò)維護(hù)一個(gè)最小堆，一個(gè)最大堆，當(dāng)push元素時(shí)，將這兩個(gè)元素連接到一起。當(dāng)pop最大或者最小的元素時(shí)，對(duì)應(yīng)刪除另一個(gè)堆中對(duì)應(yīng)的元素。
#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);
}
}
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫(xiě)作最大的動(dòng)力，如果您喜歡我的文章，感覺(jué)我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
