Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
欢迎参加IJCAI 2020麻将智能体竞赛,大奖等你拿!Welcome to IJCAI 2020 Mahjong AI competition with amazing prizes! | 北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

自创算法:对顶堆算法在线求中位数 0MS

Posted by PoPoQQQ at 2014-06-11 21:14:54 on Problem 3784 and last updated at 2014-06-12 12:23:42
对顶堆,又叫中根堆、上下堆,是一种可以LOGN维护在线求中位数的算法
思想是维护两个堆,一个小根堆,一个大根堆,保证大根堆中的任意元素小于小根堆,并维护两堆元素数平衡
其中一堆堆顶即为中位数

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
void swap(int &x,int &y){int z=x;x=y;y=z;}
int topheap[5010],toptop,bottomheap[5010],bottomtop;//两个堆,其中上堆是小根堆,下堆是大根堆 
void topinsert(int x)//上堆插入 
{
	topheap[++toptop]=x;
	int t=toptop;
	while(t>1&&topheap[t]<topheap[t>>1])
	swap(topheap[t],topheap[t>>1]),t>>=1;
}
void bottominsert(int x)//下堆插入 
{
	bottomheap[++bottomtop]=x;
	int t=bottomtop;
	while(t>1&&bottomheap[t]>bottomheap[t>>1])
	swap(bottomheap[t],bottomheap[t>>1]),t>>=1;
}
void toppop()//上堆弹顶 
{
    int t=2;
    topheap[1]=topheap[toptop];topheap[toptop--]=0;
    while(t<=toptop)
   	{	
   	    if(topheap[t]>topheap[t+1]&&t<toptop)t++;
   	    if(topheap[t]<topheap[t>>1])swap(topheap[t],topheap[t>>1]),t<<=1;
   	    else break;
   	}
}
void bottompop()//下堆弹顶 
{
    int t=2;
    bottomheap[1]=bottomheap[bottomtop];bottomheap[bottomtop--]=0;
    while(t<=bottomtop)
   	{	
   	    if(bottomheap[t]<bottomheap[t+1]&&t<bottomtop)t++;
   	    if(bottomheap[t]>bottomheap[t>>1])swap(bottomheap[t],bottomheap[t>>1]),t<<=1;
   	    else break;
   	}
}
void add(int x)//插入 
{
	if(x<=bottomheap[1])bottominsert(x);
	else topinsert(x);
	//插入,保证下堆的任意元素都小于等于上堆的任意元素  
	//注意一定要和下堆堆顶比较,因为第一次插入后元素一定在下堆,如果和上堆堆顶比较就会WA  
	while(toptop>bottomtop)bottominsert(topheap[1]),toppop();
	while(bottomtop>toptop+1)topinsert(bottomheap[1]),bottompop();
	//维护上下堆平衡,保证两堆元素数相等或下堆元素数比上堆元素数多1  
}
int ans[1010][5010];
int main()
{
	int p,i,j,k,x,m;
	scanf("%d",&p);
	for(j=1;j<=p;j++)
	{
		scanf("%d%d",&i,&m);
		memset(topheap,0,sizeof topheap);
		memset(bottomheap,0,sizeof topheap);
		toptop=bottomtop=0;
		for(k=1;k<=m;k++)
		{
			scanf("%d",&x);add(x);
			if(k&1)ans[i][++ans[i][0]]=bottomheap[1];
		}
	}
	for(i=1;i<=p;i++)
	{
		printf("%d %d\n",i,ans[i][0]);
		for(j=1;j<=ans[i][0];j++)
		{
			printf("%d",ans[i][j]);
			if(j!=ans[i][0])printf(" ");
			if(j%10==0)printf("\n");
		}
		printf("\n");
	}
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator