简答题
偏难
#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<bits/stdc++.h>
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<=x/i;i++){
for(;x%i==0;x/=i){
a[++cnt]=i;
}
}
if(x>1)a[++cnt]=x;
for(int i=1;i<=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<=n;i++){
if(n%i==0){
return 0;
}
}
return 1;
}
struct node{
int tmp;
int cs;
bool operator<(const node &b)const{
if(cs!=b.cs)return cs<b.cs;
else return tmp<b.tmp;
}
};
struct node1{
int tmp;
int cs;
bool operator<(const node1 &b)const{
if(cs!=b.cs)return cs>b.cs;
else return tmp>b.tmp;
}
};
priority_queue<node>q1;
priority_queue<node1>q2;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>num;
for(int i=1;i<=num;i++){
for(int j=1;j<=10;j++){
cin>>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<<q1.top().tmp<<" "<<q2.top().tmp<<endl;
q1.pop();q2.pop();
}
return 0;
}</pre>
这道题暂未补解析。