欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  数据库

[U]3.1.3 Humble Numbers 技巧题

程序员文章站 2022-04-17 19:36:34
...

这个题呢.... 这样: 输入数据中给了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
#include
using namespace std;

int num[111];
int list[111111];
int index[111];

bool cmp( int a,int b ){ return anum[i]*list[index[i]] )
 	 	   		{
 	 	   			min=num[i]*list[index[i]];
 	 	   			l=i;
				}
		   if( min