自动搬运

查看原文

来自洛谷，原作者为

	Leap_Frog 是啊……你就是那只鬼了……所以被你碰到以后，就轮到我变成鬼了

搬运于2025-08-24 21:38:41，当前版本为作者最后更新于2020-06-28 11:21:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P.S.

此题较为毒瘤，需要开long long以及加优化。
普通的构造方法貌似不能过QwQ。

Problem.

给定一堆质因数，求这些质因数构成（乘积）的所有数中的第K小值。

Solution.

首先，我们一看到这道题，笔者第一时间想到要用STL中的set来构造。
于是就写了一个简单的代码（解释在代码注释中）。
因为小的数$\times$

#include<bits/stdc++.h>//万能头
using namespace std;
int n,k,a[105];set<int>s;//STL set万岁
int main()
{
	scanf("%d%d",&n,&k),s.insert(1);//插入1
	for(int i=1;i<=n;i++) scanf("%d",a+i);//读入n个质因数
	for(int i=1;i<k;i++)//因为要求第k大，所以要删去k-1个比它小的数
	{
		int t=*s.begin();s.erase(s.begin());//把当前最小的拿出来并删去
		for(int i=1;i<=n;i++) s.insert(t*a[i]);//构造出当前最小的能到达的所有数
	}
	return printf("%d\n",*s.begin()),0;//输出删去k-1个最小数后的第k个
}

然后结果我们一运行。。。$\color{red}\texttt{WOC}\text{怎么样例都不过啊}$
然后我们再来仔细读一读题目

比如说至多只包含质因数2，3的数有2,3,4,6,8,9,……

好罢被坑了，1是无法构造出来的，所以要求第k个质因数是第k+1个。
恭喜笔者绕过了第一个弯QAQ。

然后笔者再打出这样一份代码

#include<bits/stdc++.h>
using namespace std;
int n,k,a[105];set<long long>s;
int main()
{
	scanf("%d%d",&n,&k),s.insert(1);
	for(int i=1;i<=n;i++) scanf("%d",a+i);
	for(int i=1;i<=k;i++)//修改唯一一处：<k变成<=k
	{
		int t=*s.begin();s.erase(s.begin());
		for(int i=1;i<=n;i++) if(t*a[i]<=2000000000) s.insert(t*a[i]);
	}
	return printf("%lld\n",*s.begin()),0;
}

样例是过了，但是$\color{red}\texttt{WOC}\text{为什么}\texttt{WA40}\text{啊}$
笔者仔细地看了看错误信息。

Wrong Answer. wrong answer On line 1 column 1, read -, expected 6.

好罢，知道了，没开long long。
恭喜笔者绕过了第二个弯。

然后笔者又打出了第三份代码

#include<bits/stdc++.h>
using namespace std;
int n,k,a[105];set<long long>s;//修改：int变成long long
int main()
{
	scanf("%d%d",&n,&k),s.insert(1);
	for(int i=1;i<=n;i++) scanf("%d",a+i);
	for(int i=1;i<=k;i++)
	{
		long long t=*s.begin();s.erase(s.begin());//修改：int变成long long
		for(int i=1;i<=n;i++) s.insert(t*a[i]);
	}
	return printf("%lld\n",*s.begin()),0;
}

WA是不WA了，但是$\color{red}\texttt{WOC}\text{为什么}\texttt{T}\text{了一个点啊}$
笔者随便加了点优化。

#include<bits/stdc++.h>
using namespace std;
int n,k,a[105];set<long long>s;
int main()
{
	scanf("%d%d",&n,&k),s.insert(1);
	for(int i=1;i<=n;i++) scanf("%d",a+i);
	sort(a+1,a+n+1);//排个序更快
	for(int i=1;i<=k;i++)
	{
		long long t=*s.begin();s.erase(s.begin());
		for(int i=1;i<=n;i++) if(t*a[i]<=2000000000) s.insert(t*a[i]);
		//因为题目中已经说了，保证答案不超过2000000000。
		//那么超过2000000000的肯定不需要加入set，一个优化
	}
	return printf("%lld\n",*s.begin()),0;
}

结果还是$\color{red}\texttt{T}$

于是笔者从整份代码来考虑，T的原因应该是在set中加入太多超过第K大的数了吧。
那么我们可以记录当前set的最大值。
如果的接下来构造的这个数已经大于最大值且set中有k个数了。
我们就可以break结束了。
然后加了这个优化之后，笔者顺利AC了这道题QAQ。

Coding.

#include<bits/stdc++.h>
using namespace std;
int n,k,f=1,a[105];long long mx,INF=2000000000;set<long long>s;
//f表示当前set中是否有k个数
int main()
{
	scanf("%d%d",&n,&k),s.insert(1);
	for(int i=1;i<=n;i++) scanf("%d",a+i),a[i]==1?(i--,n--):0;
	sort(a+1,a+n+1),mx=1;//最大值变成当前唯一的一个1
	for(int i=1;i<=k;i++)
	{
		long long t=*s.begin();s.erase(s.begin());
		for(int i=1;i<=n&&t*a[i]<=INF;i++) if(f||a[i]*t<=mx) s.insert(t*a[i]),mx=max(mx,t*a[i]);
		//首先，刚刚加的优化仍然有（在循环条件中）
		//然后，这个判断条件就是刚刚说的那个break的反条件QAQ
		f=((int)s.size()+i<=k);
		//更新f，检查加入后是否set中有k个数
	}
	return printf("%lld\n",*s.begin()),0;
}

Ending.

写题解辛苦，管理大大求过，无耻求赞