洛谷 P2527 [SHOI2001]Panda的烦恼 题解【枚举】【贪心】

作者: wjyyy 分类: 枚举,解题报告,贪心 发布时间: 2018-06-26 22:02

点击量:19

 

   所以这个题是模拟优先队列???

 

题目描述

panda是个数学怪人,他非常喜欢研究跟别人相反的事情。最近他正在研究筛法,众所周知,对一个范围内的整数,经过筛法处理以后,剩下的全部都是质数,不过panda对这些不感兴趣,他只对被筛掉的数感兴趣,他觉得在这些被筛掉的数中一定隐藏着重要的宇宙秘密,只是人们还没有发现罢了。

 

panda还觉得如果只是单纯地从小到大筛的话,还不足够发现其中的奥秘,于是他决定对至多只包含某些质因数的数进行研究(比如说至多只包含质因数2,3的数有2,3,4,6,8,9,……),他需要得到这些数中第k小的数(k是panda认为的宇宙系数),请你编个程序,帮助他找到这个数。

 

输入输出格式

输入格式:

第1行有2个数n,k,n代表质因数的个数,k代表那个宇宙系数(1<=n<=100,1<=k<=100000)

 

第2行有n个数,代表这n个质因数。(每个均小于1000,且不相同)

 

输出格式:

仅1行,即至多只包含这n个质因数的数中第k小的数。(这个数不会超过2000000000)

 

输入输出样例

输入样例#1:
2 7
3 5
输出样例#1:
45

说明

样例说明:前6个分别是3,5,9,15,25,27。

 

   N×K就刚好一亿了,这个题的做法也就刚好N×K,而用堆/set维护,k越大要么会TLE要么就MLE或RE了,总之是做不了完美的。

 

   那么我们实际上可以用枚举的方式找出最大值,因为我们每次选最小值,选出来筛选掉,那么每次就枚举该乘哪个数。根据贪心,乘法是质数互相乘,每个数要乘的数一定是从小到大枚举,那么我们在没乘过的里找乘积的最小值。因为所有数下一个要乘的都是未来乘积里最小的,也是未来所有数乘积最小的,所以在n×k的复杂度内,可以完成。

 

   不过要注意,可能会有数重复得出结果,这样我们就要排除这些比ans[cnt]相等或更小的,才能得出正确答案。

 

   原来贪心才是世界上最毒瘤的题啊23333…

 

Code:

#include<cstdio>

int pri[105];//质数
int ans[100010],cnt=0;//答案
int p[105];//该乘哪个数了
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&pri[i]);
        ans[0]=1;
    }

    for(int i=1;i<=k;i++)
    {
        long long minn=0x7fffffff,tmp=0;
        for(int j=1;j<=n;j++)
        {
            while((long long)pri[j]*ans[p[j]]<=ans[cnt])//注意去重
                p[j]++;
            if((long long)pri[j]*ans[p[j]]<minn)//找最小值
            {
                minn=pri[j]*ans[p[j]];
                tmp=j;
            }
        }

        ans[++cnt]=minn;
        p[tmp]++;
    }
    printf("%d",ans[k]);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */