谦虚数字(由AcWing 62. 丑数推导而来)
同AcWing 62. 丑数 (3路归并排序):
丑数那道题的思想是以2,3,5为基准,初始把所有2,3,5指向res[0]=1(res数组代表最终序列,now数组代表下标)(初始now[2]=now[3]=now[5]=0(注意0是下标))
初始now指向1 * 2;1 * 3;,1 * 5(对应的下标乘自己对应的数)
然后res数组每次pushback一个当前最小的数这里是1 * 2=2(此时res={1,2})
然后对应的下标now[2]++,此时now[2]=1,所以对应的值就是res[now[2]]=2
所以此时now[2]对应上的数就是2 * 2=4,下一轮pushback当前最小的数就是1 * 3=3,以此类推
(要注意每一轮push完一个数要遍历每一个now,看now对应的下标映射的值是否与这个数相等,凡是相等的now对应的下标都要++(去重))
这样记录可以保证
1:不重:
同上一段最后一句.每一轮相等的数字都会被筛掉
2:不漏:
从小到大把初始基准的数2,3,5,以及”以2,3,5为质因子的数”取出(取出的数一定是当前的最小值,因为每一个now对应的下标映射的值一定是递增的 )
3:合法:
以2,3,5为基准的数得到的一定以2,3,5为质数,以”以2,3,5为质因子的数”的数为基准的数得到的一定还是以2,3,5为质因子的数字
本道题和丑数相同,只不过2,3,5变成了一个质数序列而已,每次取最小的res[now[i]]*q[i]
(now含义同第三行,q[i]含义同2,3,5)
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
int n,k;
priority_queue<int,vector<int>,greater<int>>pri;
vector<int>res;
int q[110],now[110];
void solve()
{
cin>>k>>n;
for(int i=1;i<=k;i++)
cin>>q[i];
res.pb(1);
while(n--)
{
int mi=INF;
for(int i=1;i<=k;i++)
mi=min(mi,res[now[i]]*q[i]);
res.pb(mi);
// cout<<mi<<endl;
for(int i=1;i<=k;i++)
if(res[now[i]]*q[i]==mi)now[i]++;
}
cout<<res.back()<<endl;
}
signed main()
{
int T=1;
//cin>>T;
while(T--)
solve();
return 0;
}
太清晰了!!!
哇,大佬的题解好清晰呀,一看就懂了,感谢大佬,STO