这个题呢.... 这样： 输入数据中给了4个质数 2 3 5 7。 我们就有4个队列 2-----2 3 5 7 3-----3 5 7 5-----5 7 7-----7 每个队列乘以队列的第一个数，取出乘积的最小，插入到队列中。 例如当前的最小为2*2=4，插入队列 2------3 4 5 7 3------3 4 5 7 5-----
这个题呢.... 这样：
输入数据中给了4个质数
2 3 5 7。
我们就有4个队列
2-----2 3 5 7
3-----3 5 7
5-----5 7
7-----7
每个队列乘以队列的第一个数，取出乘积的最小值，插入到队列中。
例如当前的最小值为2*2=4，插入队列
2------3 4 5 7
3------3 4 5 7
5------4 5 7
7------4 7
可以看到插入的值可能在队列中间也可能在队列末端。
1.在队列中间：进行一次排序保证插入顺序。
2.在队列末端：不需要进行排序，直接插入最尾端保持有序。
因此，将最大的质数作为判断准则，就能得出数的插入位置。
对于每个质数的队列，只需要标记坐标。
另外判重的问题：
1.如果当前插入的乘积比最大质数小，则很有可能在序列的中部分发生冲突，遍历一部分队列就好。
2.插入的乘积比最大质数大，直接判断队列末端是否重复。
时间还不错~
Code：
/*
ID:sevenst4
LANG:C++
PROG:humble
*/
#include<stdio.h>
#include<algorithm>
using namespace std;
int num[111];
int list[111111];
int index[111];
bool cmp( int a,int b ){ return a<b; }
bool judge( int a,int len )
{
for( int i=1;i<=len;i++ )
if( list[i]==a )
return false;
return true;
}
int main()
{
freopen( "humble.in","r",stdin );
freopen( "humble.out","w",stdout );
int k,n;
scanf( "%d %d",&k,&n );
for( int i=1;i<=k;i++ )
{
scanf( "%d",&num[i] );
list[i]=num[i];
index[i]=i;
}
int top=num[k];
int cnt=k;
while( cnt<n )
{
int l;
int min=0x7FFFFFFF;
for( int i=1;i<=k;i++ )
if( min>num[i]*list[index[i]] )
{
min=num[i]*list[index[i]];
l=i;
}
if( min<list[cnt] )//向前插入
{
if( judge( min,cnt ) )//合法
list[++cnt]=min;
}
else if( list[cnt]!=min )//在最后面插入
list[++cnt]=min;
if( min<=top )
sort( list+1,list+cnt+1,cmp );
index[l]++;
}
printf( "%d\n",list[n] );
return 0;
}
