posts - 33,  comments - 33,  trackbacks - 0
题意:
给出两种操作:ADD(x),将x添加到有序列表中;GET()返回全局迭代器所指的值,其中迭代器在GET操作后会自添加1
题解:
刚开始直接手打链表模拟,结果超时。这时应使用另外一种方法:使用大顶堆和小顶堆。
其中,对于序列S[1..n],及表示迭代器位置的index,大顶堆维护排序后的S[1..index-1],小顶堆维护
排序后的S[index..n],例如S[1..n] = 1,2,3,4,5,6,7,index = 4,则大顶堆为{1,2,3},小顶堆为{4,5,6,7}
为什么要这样维护呢?因为当小堆最小的元素都大于大堆最大的元素时,那么序列中排第n个就是小堆最小的数了。
我们假设第k趟GET()后,有以下情景(GET后k自动加1):
大顶堆:S[1..k],堆顶元素为S[k],小顶堆:S[k+1,n],堆顶元素为S[k+1],然后每当添加一个元素newE时,先添加到大顶堆中,这时如果出现大顶堆数大于小顶堆的数时,理应交换。
代码:
#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 阅读(1691) 评论(0)  编辑 收藏 引用 所属分类: 算法题解

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理