P2527 [SHOI2001]Panda的烦恼 题解

· · 题解

一篇用 priority_queue AC 的题解。

思路：先把 p_{i} 全部扔到优先队列（小顶堆）里，每次取出队首。先判断有没有重复，如重复了就直接弹出队列，否则把 top \times p_{i} 扔到优先队列里。

这样做只有 90 pts，所以我们充分发扬人类智慧。

优化：第一个点超了 0.1 s，非常离谱。 我们发现，当 n 较大时，有些 p_{i} 也较大，在队内已有较多元素时，top \times p_{i} 只有在 p_{i} 较小时才有可能在前 k 个。于是，我们在已经弹出一半（确定了前 \dfrac{k}{2} ）以后只取前 5 个 p_{i}（ p{i} 从小到大排序，n 较大）。

代码如下：

#include<iostream>
#include<cstdio>
#include<string.h>
#include<cmath>
#include<queue>
#include<algorithm>
#include<deque>
#include<vector> 
using namespace std;
typedef long long ll;
priority_queue<ll,vector<ll>,greater<ll> > q;
int n,k;
int p[101];
int tot;
vector<ll> ans;
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&p[i]);
        q.push(p[i]);
    }
    sort(p+1,p+1+n);
    ans.push_back(0);
    while(tot<=k)
    {
        ll now=q.top();
        if(now!=ans[tot])
        {
            tot++;
            ans.push_back(now); 
            int t=n;
            if(tot>k/2)
            {
                t=min(n,5);
            }   
            for(int i=1;i<=t;i++)
            {
                q.push(now*p[i]);
            }
        }
        q.pop();
    }
    printf("%lld\n",ans[k]);
}

PS：格式错误已修改，望通过。