題意：
給出兩種操作：ADD(x)，將x添加到有序列表中；GET()返回全局迭代器所指的值，其中迭代器在GET操作后會(huì)自添加1
題解：
剛開始直接手打鏈表模擬，結(jié)果超時(shí)。這時(shí)應(yīng)使用另外一種方法：使用大頂堆和小頂堆。
其中，對于序列S[1..n]，及表示迭代器位置的index，大頂堆維護(hù)排序后的S[1..index-1]，小頂堆維護(hù)
排序后的S[index..n],例如S[1..n] = 1,2,3,4,5,6,7，index = 4，則大頂堆為{1,2,3}，小頂堆為{4,5,6,7}
為什么要這樣維護(hù)呢？因?yàn)楫?dāng)小堆最小的元素都大于大堆最大的元素時(shí)，那么序列中排第n個(gè)就是小堆最小的數(shù)了。
我們假設(shè)第k趟GET()后，有以下情景(GET后k自動(dòng)加1)：
大頂堆：S[1..k]，堆頂元素為S[k]，小頂堆：S[k+1,n]，堆頂元素為S[k+1]，然后每當(dāng)添加一個(gè)元素newE時(shí)，先添加到大頂堆中，這時(shí)如果出現(xiàn)大頂堆數(shù)大于小頂堆的數(shù)時(shí)，理應(yīng)交換。
代碼：
#include <queue>
#include <stdio.h>
using namespace std;
int m,n;
int sequence[30005];
struct cmp1
{
bool operator()(const int a,const int b)
{
return a>b;
}
};
struct cmp2
{
bool operator()(const int a,const int b)
{
return a<b;
}
};
void Test()
{
priority_queue<int,vector<int>,cmp1>q1;//小堆
priority_queue<int,vector<int>,cmp2>q2;//大堆
for (int i = 0; i < m; ++i)
{
scanf("%d",&sequence[i]);
}
int op;
int k = 0;
for (int i = 0; i < n; ++i)
{
scanf("%d",&op);
while(k < op)
{
q1.push(sequence[k]);
if (!q2.empty() && q1.top() < q2.top())
{
int t1 = q1.top();
q1.pop();
int t2 = q2.top();
q2.pop();
q1.push(t2);
q2.push(t1);
}
++k;
}
printf("%d\n",q1.top());
q2.push(q1.top());
q1.pop();
}
}
int main()
{
while(scanf("%d %d",&m,&n) != EOF)
{
Test();
}
return 0;
}posted on 2011-06-02 15:34
bennycen 閱讀(1699)
評論(0) 編輯 收藏 引用 所屬分類:
算法題解