【Luogu P1168】【Luogu P1801&UVA 501】中位数&黑匣子（Black Box）—

Luogu P1168

Luogu P1801

UVA 501（洛谷Remote Judge）

前置知识：堆、优先队列STL的使用

对顶堆

是一种在线维护第\(k\)小的算法。

其实就是开两个堆，一个是大根堆，一个是小根堆。两个堆的根相对。

下面借助题目P1168进行详细分析。

P1168

题意很好理解，不多作分析。

显然当\(i=1\)时，中位数就是\(a[1]\)，记为\(mid\)。

我们可以使用对顶堆，把比\(mid\)小的存入大根堆，比mid大的存入小根堆。

当我们已经加入奇数个元素时，可以根据两个堆的大小调整\(mid\)值

当\(heap-big.size==heap-little.size\)，当前\(mid\)即为中位数
当\(heap-big.size<heap-little.size\)，将当前\(mid\)压入大根堆，小根堆的堆顶弹出并作为新的mid，重复以上过程直至\(heap-big.size==heap-little.size\)。
反之同理

那么这样不断操作就可以求出答案了。

#include<cstdio>

#include<queue>

using namespace std;

priority_queue<int> que1;//大根堆

priority_queue<int,vector<int>,greater<int>> que2;//小根堆

int n,a,mid;

int main()

{

	scanf("%d",&n);

	scanf("%d",&a);

	mid=a;

	printf("%d\n",a);

	for (int i=2;i<=n;i++)

	{

		scanf("%d",&a);

		if (a>mid) que2.push(a);

		if (a<=mid) que1.push(a);

		if (i%2==1)

		{

			if (que1.size()!=que2.size())

			{

				//不用while是因为两个堆的大小最多相差2。

				if (que1.size()>que2.size())

				{

					que2.push(mid);

					mid=que1.top();

					que1.pop();

				}

				else

				{

					que1.push(mid);

					mid=que2.top();

					que2.pop();

				}

			}

			printf("%d\n",mid);

		}

	}

	return 0;

}

P1801&UVA 501

思路类似，不再重复

P1801

#include<queue>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

priority_queue<int,vector<int>,greater<int> > que2;

priority_queue<int,vector<int>,less<int> > que1;

int m,n,a[200005],T,u[200005];

int main()

{

	//scanf("%d",&T);

	T=1;

	/*这是根据UVA 501修改的，两题其实是一样的，但是UVA 501有多组数据，且对输出格式

	有要求*/

	while (T--)

	{

		while (!que1.empty()) que1.pop();

		while (!que2.empty()) que2.pop();

		memset(a,0,sizeof(a));

		memset(u,0,sizeof(u));

		scanf("%d%d",&m,&n);

		for (int i=1;i<=m;i++)

			scanf("%d",&a[i]);

		for (int i=1;i<=n;i++)

			scanf("%d",&u[i]);

		int j=1,now=u[1];

		for (int i=1;i<=m;i++)

		{

			if (que1.empty()) que1.push(a[i]);

			else if (a[i]<que1.top()) que1.push(a[i]);

			else que2.push(a[i]);

			if (i==now)

			{

				while (i==now)

				{

					while (que1.size()<j)

					{

						que1.push(que2.top());

						que2.pop();

					}

					while (que1.size()>j)

					{

						que2.push(que1.top());

						que1.pop();

					}

					printf("%d\n",que1.top());

					j++;

					now=u[j];

					if (j>n) return 0;

				}

			}

		}

		if (T) printf("\n");

	}

	return 0;

}

UVA 501

#include<queue>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

priority_queue<int,vector<int>,greater<int> > que2;

priority_queue<int,vector<int>,less<int> > que1;

int m,n,a[200005],T,u[200005];

int main()

{

	scanf("%d",&T);

	while (T--)

	{

		while (!que1.empty()) que1.pop();

		while (!que2.empty()) que2.pop();

		memset(a,0,sizeof(a));

		memset(u,0,sizeof(u));

		scanf("%d%d",&m,&n);

		for (int i=1;i<=m;i++)

			scanf("%d",&a[i]);

		for (int i=1;i<=n;i++)

			scanf("%d",&u[i]);

		int j=1,now=u[1];

		for (int i=1;i<=m;i++)

		{

			if (que1.empty()) que1.push(a[i]);

			else if (a[i]<que1.top()) que1.push(a[i]);

			else que2.push(a[i]);

			if (i==now)

			{

				while (i==now)

				{

					while (que1.size()<j)

					{

						que1.push(que2.top());

						que2.pop();

					}

					while (que1.size()>j)

					{

						que2.push(que1.top());

						que1.pop();

					}

					printf("%d\n",que1.top());

					j++;

					now=u[j];

					if (j>n) break;

				}

				if (j>n) break;

			}

			if (j>n) break;

		}

		if (T) printf("\n");

	}

	return 0;

}

巴特西

【Luogu P1168】【Luogu P1801&UVA 501】中位数&黑匣子（Black Box）——对顶堆相关

对顶堆

P1168

P1801&UVA 501

P1801

UVA 501

最新文章

热门文章