luogu2723 丑数

提供一种单调队列做法(非正解)

显然每一个丑数能够由一个质数乘以另一个丑数得到

所以我们开k个单调递增队列，每次从这些队列顶部找到一个最小的元素把他捞出来，然后枚举所有质数，用这个元素乘以质数，放入相应的单调队列里。找到的第n个数就是所求的丑数。由于会有重复，但是取出元素的顺序是单调的，所以开一个last变量判重。

本代码不开O2卡一个点(下载下来跑1200ms)，开O2过。（因为我用的STL的队列23333）

#include <bits/stdc++.h>

using namespace std;

struct data

{

	int x;

	queue<int> q;

	friend bool operator>(const data &aa, const data &bb);

}t, a[110];

int k, n;

bool operator>(const data &aa, const data &bb)

{

	return aa.q.front() > bb.q.front();

}

int main()

{

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

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

	{

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

		a[i].q.push(a[i].x);

	}

	int last = 1;

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

	{

		int minj = 1;

		for (int j = 2; j <= k; j++)

		{

			if (a[minj] > a[j])

				minj = j;

		}

		int xx = a[minj].q.front();

		a[minj].q.pop();

		if(last == xx)

		{

			i--;

			continue;

		}

		for (int j = 1; j <= k; j++)

		{

			a[j].q.push(a[j].x * xx);

		}

		last = xx;

		if (i == n)

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

	}

	return 0;

}

巴特西

luogu2723 丑数

最新文章

热门文章