G:priority queue练习题 — STL

G:priority queue练习题

总时间限制: 2500ms 内存限制: 131072kB

描述

我们定义一个正整数a比正整数b优先的含义是：
*a的质因数数目（不包括自身）比b的质因数数目多；
*当两者质因数数目相等时，数值较大者优先级高。

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

输入

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

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

输出

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

样例输入

1
10 7 66 4 5 30 91 100 8 9

样例输出

66 5

练习一下手写cmp

#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define inf 1000000007
#define ll long long
#define N 10000010
inline int rd()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int sz[N],prm[N>>3],cnt;
void INIT(){
    memset(sz,-1,sizeof(sz));
    for(int i=2;i<N;++i){
        if(!(~sz[i])) prm[++cnt]=i,sz[i]=0;
        for(int j=1;j<=cnt;++j){
            if(prm[j]*i>=N) break;
            sz[prm[j]*i]=max(sz[i],1);
            if(i%prm[j]==0) break;
            ++sz[prm[j]*i];
        }
    }
}
struct cmp{
    bool operator()(int &a, int &b){
        return sz[a]==sz[b]?a<b:sz[a]<sz[b];
    }
};
int T;
priority_queue<int,vector<int>,cmp>q;
int tp[310],tot;
int main()
{
    INIT();
    T=rd();
    while(T--){
        for(int i=0;i<10;++i) q.push(rd());
        printf("%d ",q.top());q.pop();
        tot=0;
        while(!q.empty()){
            tp[++tot]=q.top();
            q.pop();
        }
        printf("%d\n",tp[tot]);
        for(int i=1;i<tot;++i) q.push(tp[i]);
    }
    return 0;
}