PAT Basic 1030 完美数列 (25 分)

PAT Basic 1030 完美数列 (25 分)
强烈推介IDEA2021.1.3破解激活,IntelliJ IDEA 注册码,2021.1.3IDEA 激活码  

大家好,我是架构君,一个会写代码吟诗的架构师。今天说一说PAT Basic 1030 完美数列 (25 分),希望能够帮助大家进步!!!

给定一个正整数数列,和正整数 p,设这个数列中的最大值是 M,最小值是 m,如果 Mmp,则称这个数列是完美数列。

现在给定参数 p 和一些正整数,请你从中选择尽可能多的数构成一个完美数列。

输入格式:

输入第一行给出两个正整数 N 和 p,其中 N(≤)是输入的正整数的个数,p(≤)是给定的参数。第二行给出 N 个正整数,每个数不超过 1。

输出格式:

在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。

输入样例:

10 8
2 3 20 4 5 1 6 7 8 9

输出样例:

8



#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int N,p;
    cin>>N>>p;
    long long a[N];
    for(int i=0;i<N;i++)
        cin>>a[i];
    sort(a,a+N);
    int res=0;
    for(int i=0;i<N;i++){
        for(int j=i+res;j<N;j++){
            if(a[j]<=a[i]*p) res++;
            else break;
        }
    }
    cout<<res;
    system("pause");
}

1个超时点分析:

1.你如果没有用2个循环,那么概念有错

测试用例:

10 8
1 2  3 4 5 6 7 8 9 100

2.一个超时,可能是你的没有加else break,这个else break意味深长,让你的复杂度变为O(1)

测试用例:取10^5个数让你慢慢遍历

3.没有使用long long,10^9为10位数,并非9位,int的范围为2后面8个数,可能大小超出

测试用例:中间放一个3(8个0),存在这样的数会溢出

转载于:https://www.cnblogs.com/littlepage/p/11444487.html

本文来源weixin_30595035,由架构君转载发布,观点不代表Java架构师必看的立场,转载请标明来源出处:https://javajgs.com/archives/29348

发表评论