首页 › 题库 › C/C++编程考级 › C/C++编程七级 › 简答题
简答题 偏难
#7391

priority queue练习题 我们定义一个正整数a比正整数b优先的含义是: *a的质因数数目(不包括自身)比b的质因数数目多; *当两者质因数数目相等时,…

priority queue练习题

我们定义一个正整数a比正整数b优先的含义是:

*a的质因数数目(不包括自身)比b的质因数数目多;

*当两者质因数数目相等时,数值较大者优先级高。

现在给定一个容器,初始元素数目为0,之后每次往里面添加10个元素,每次添加之后,要求输出优先级最高与最低的元素,并把该两元素从容器中删除。

时间限制:2500

内存限制:131072

输入

第一行: num (添加元素次数,num <= 30)

下面10*num行,每行一个正整数n(n < 10000000).

输出

每次输入10个整数后,输出容器中优先级最高与最低的元素,两者用空格间隔。

样例输入

1
10 7 66 4 5 30 91 100 8 9

样例输出

66 5
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include&lt;bits/stdc++.h&gt; using namespace std; int num,d[35][15],pri[500010],tot[500010],a[500010]; int DECOMPOSITION(int x){   int cnt=0,Cnt=0;   for(int i=2;i&lt;=x/i;i++){     for(;x%i==0;x/=i){       a[++cnt]=i;     }   }   if(x&gt;1)a[++cnt]=x;   for(int i=1;i&lt;=cnt;i++,tot[Cnt]++){     if(a[i]!=a[i-1])pri[++Cnt]=a[i];   }   return Cnt; } bool isprime(int n){   for(int i=2;i*i&lt;=n;i++){     if(n%i==0){       return 0;     }   }   return 1; } struct node{   int tmp;   int cs;   bool operator&lt;(const node &amp;b)const{     if(cs!=b.cs)return cs&lt;b.cs;     else return tmp&lt;b.tmp;   } }; struct node1{   int tmp;   int cs;   bool operator&lt;(const node1 &amp;b)const{     if(cs!=b.cs)return cs&gt;b.cs;     else return tmp&gt;b.tmp;   } }; priority_queue&lt;node&gt;q1; priority_queue&lt;node1&gt;q2; int main(){   ios::sync_with_stdio(0);   cin.tie(0);   cout.tie(0);   cin&gt;&gt;num;   for(int i=1;i&lt;=num;i++){     for(int j=1;j&lt;=10;j++){       cin&gt;&gt;d[i][j];       int cyt=DECOMPOSITION(d[i][j]);       if(d[i][j]==1||d[i][j]==0||isprime(d[i][j]))cyt=0;       node top1 ;;       node1 top2;       top1.tmp=d[i][j];       top1.cs=cyt;       top2.tmp=d[i][j];       top2.cs=cyt;       q1.push(top1);       q2.push(top2);     }     cout&lt;&lt;q1.top().tmp&lt;&lt;" "&lt;&lt;q2.top().tmp&lt;&lt;endl;     q1.pop();q2.pop();   }   return 0; }</pre>
这道题暂未补解析。