每次找下一個最小的humble數(shù)直到第n個為止。
對每一個prime，用二分法找出乘以已有的humble數(shù)且>=現(xiàn)有最大的humble數(shù)的最小的那一個。
然后取最小的那一個作為新找到的humble數(shù)。
開始的時候最后一個例子總是超時，后來用一個next_min數(shù)組緩存一下結(jié)果，效率一下提高了10倍。
#include?<iostream>
#include?<fstream>
using?namespace?std;
int?humbles[100002];
int?primes[100];
int?k,n;
int?top;
int?next_min[100];
long?long?find_next(int?i)
{
????int?l?=?0;
????int?h?=?top;
????int?mid;
????while(l<=h){
????????mid?=?(l+h)/2;
????????if((long?long)humbles[mid]*primes[i]<=humbles[top]){
????????????l?=?mid+1;
????????}else{
????????????h?=?mid-1;
????????}
????}
????return?humbles[h+1]*primes[i];
}
void?solve()
{
????humbles[0]?=?1;
????top?=?0;
????freopen("humble.in","r",stdin);
????freopen("humble.out","w",stdout);
????scanf("%d%d",&k,&n);
????for(int?i=0;i<k;++i)
????????scanf("%d",&primes[i]);
????for(int?i=0;i<k;++i)
????????next_min[i]?=?find_next(i);
????while(top<n){
????????long?long?next?=?LONG_MAX;
????????long?long?tmp;
????????for(int?i=0;i<k;++i){
????????????if(next_min[i]<=humbles[top])
????????????????tmp?=?next_min[i]?=?find_next(i);
????????????else
????????????????tmp?=?next_min[i];
????????????if(tmp<next){
????????????????next?=?tmp;
????????????}
????????????if(next==humbles[top]+1)
????????????????break;
????????}
????????humbles[++top]?=?next;
????}
????printf("%d\n",humbles[n]);
}
int?main(int?argc,char?*argv[])
{
????solve();?
????return?0;
}