PAT 乙级 1030 完美数列

2023-12-28 04:34:50

在这里插入图片描述

解题思路:这道题首先需要排序,然后双循环找出最大的那个,但一定要注意优化,比如我已经刚好找到临界,或者之后的不用遍历了没意义了,要赶紧跳出循环,否则会超时,另外其实这题还有个范围的坑过,因为乘法一旦用int,会溢出,只能用long long int ,不推荐用double去弄,原因跟之前的理由一样,就是存储方式不同,很容易在极特殊的测试点卡住,我的原则是能不用double就不用double,python就不用想这些了写起来更容易。

c语言代码如下:

#include<stdio.h>
#include<stdlib.h>
int cmp(const void *a,const void *b)
{
	return *(int *)a-*(int *)b;
}
int input(int *a,int n)
{
	int i;
	for(i=0;i<n;i++)
	scanf("%d",a+i);
	return 1;	
}
int main()
{
	int n,a[100001],i,j,output=0;    //output就是我们要的结果 
	long long p,max=0;          //为了计算不溢出 
	scanf("%d %lld",&n,&p);
	input(a,n);
	qsort(a,n,sizeof(int),cmp);     //排序 
	for(i=0;i<n;i++)
	{
		for(j=i+output;j<n;j++)
		{
			max=p*a[i];
			if(max>=a[j])
			{
				if(output<j-i+1)
				{
					output=j-i+1;  //更新output 
				}
			}
			else
			break;	 //这后面的循环已经没有意义了,因为是排过序的,赶紧跳出,不然会超时 
		}
	}
	printf("%d\n",output);
	return 0;
 } 

在这里插入图片描述

python:

s=input().split()
a=input().split()
for i in range(0,len(a)):
    a[i]=int(a[i])
a.sort()
n=int(s[0])
p=int(s[1])
output=0
for i in range(0,n):
    for j in range(output+i,n):
        max=a[i]*p
        if(max>=a[j]):
            if(j-i+1>output):
                output=j-i+1
        else:
            break;
print(output)

注意测试点4 偶尔提交python可以通过偶尔通过不了

在这里插入图片描述

文章来源:https://blog.csdn.net/qq_44063802/article/details/135245761
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。