數據結構問題，雙向優先隊列維護，每次插入一些元素，取出最大值和最小值。可以用兩個堆維護，在一個堆中刪除後相應在另一個堆中也刪除。也可以用平衡樹，下面是我的Treap的代碼。

/* 
 * Problem: POI2000 pro
 * Author: Guo Jiabao
 * Time: 2008.12.22 20:35
 * State: Solved
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

using namespace std;

class tTreap
{
    private:
        class tNode
        {
            public:
                tNode *left,*right;
                int v,fix;
                tNode(int tv): v(tv),left(0),right(0)
                {
                    fix=rand();
                }
        };
        tNode *root;
        int R;
        void rot_r(tNode *&P)
        {
            tNode *Q=P->left;
            P->left=Q->right;
            Q->right=P;
            P=Q;
        }
        void rot_l(tNode *&P)
        {
            tNode *Q=P->right;
            P->right=Q->left;
            Q->left=P;
            P=Q;
        }
        void _ins(tNode *&P,int v)
        {
            if (!P)
                P=new tNode(v);
            else if (v<P->v)
            {
                _ins(P->left,v);
                if (P->left->fix < P->fix)
                    rot_r(P);
            }
            else
            {
                _ins(P->right,v);
                if (P->right->fix < P->fix)
                    rot_l(P);
            }
        }
        void _delete_max(tNode *&P)
        {
            if (P->right)
                _delete_max(P->right);
            else
            {
                R=P->v;
                tNode *T=P;
                P=P->left;
                delete T;
            }
        }
        void _delete_min(tNode *&P)
        {
            if (P->left)
                _delete_min(P->left);
            else
            {
                R=P->v;
                tNode *T=P;
                P=P->right;
                delete T;
            }
        }
    public:
        tTreap():root(0){}
        void ins(int v){_ins(root,v);}
        int delete_max() {_delete_max(root);return R;}
        int delete_min() {_delete_min(root);return R;}
};

int N,Ans;
tTreap Treap;

void init()
{
    freopen("pro.in","r",stdin);
    freopen("pro.out","w",stdout);
}

void solve()
{
    int M,v,A,B;
    scanf("%d",&N);
    for (int i=1;i<=N;i++)
    {
        scanf("%d",&M);
        for (int j=1;j<=M;j++)
        {
            scanf("%d",&v);
            Treap.ins(v);
        }
        A=Treap.delete_max();
        B=Treap.delete_min();
        Ans+=A-B;
    }
}

int main()
{
    init();
    solve();
    printf("%d",Ans);
    return 0;
}

<h2><span class="mw-headline">促銷活動</span></h2>

問題描述

促銷活動遵守以下規則：
<ol>
    <li>一個消費者 —— 想參加促銷活動的消費者，在賬單下記下他自己所付的費用，他個人的詳細情況，然後將賬單放入一個特殊的投票箱。</li>
    <li>當每天促銷活動結束時，從投票箱中抽出兩張賬單：</li>
</ol>

• 第一張被抽出的賬單是金額最大的賬單
• 然後被抽出的是金額最小的賬單，對於付了金額最大賬單的這位消費者，將得到一定數目的獎金，其獎金數等於他賬單上的金額與選出的最小金額的差。

• 爲了避免一個消費者多次獲獎，根據上面所抽出的兩張賬單都不返回到投票箱，但是剩下的賬單還繼續參加下一天的促銷活動。

  超市的售出額是巨大的，這樣可以假定，在每天結束，拿出數額最大賬單和數額最小賬之前，在投票箱內就已經至少存在了 2 張賬單。你的任務是去計算每天促銷活動投進投票箱的賬單數額的基本信息。在整個活動中開銷總數。

  本題中約定：

  整個活動持續了 N 天 (N<=5000) 。 第 i 天放入的帳單有 a[i] 張， a[i]<=10^5 。且 sigma(a[1]...a[n])<=10^6 。 每一天放入的帳單的面值均 <=10^6 。

  輸入格式

  輸入文件的第一行是一個整數 n （ 1 <= n <= 5000 ），表示促銷活動歷時的天數。

  以下的 n 行，每行包含若干由空格分隔的非負整數。第 i+1 行的數表示在第 i 天投入箱子的賬單金額。每行的第一個數是一個整數 k （ 0 <= k <= 10^5 ）， 表示當日賬單的數目。後面的 k 個正整數代表這 k 筆賬單的金額，均小於10^6 。

  整個活動中涉及到的賬單筆數不會超過 10^6 。

  輸出格式

  輸出文件的唯一一行是一個整數，等於整個促銷活動中應該付出的獎金總額。

  【輸入輸出樣例】

  輸入

  5
    3 1 2 3
    2 1 1
    4 10 5 5 1
    0
    1 2

  輸出

  19