1030 完美数列 (25分)

技术文章 1年前 (2020) 完美者
1,009 0

标签:nba   二分   void   sub   gis   font   str   scanf   版本   

1030 完美数列 (25分)

 

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

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

输入格式:

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

输出格式:

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

输入样例:

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

输出样例:

8


这题蛮有意思的,前几道题我答得飞快,这个有俩个测试点把我卡住了,我当时轻松看了一眼题上来就写了个递归
,俩个测试点没过,一个错误,一个超时,没关系我慢慢分析我出现的错误。。。

#include<stdio.h>             //错误版本一。
#include<stdlib.h>
int cmp(const void *a,const void *b)
{
 return *(int *)a-*(int *)b;
 
}
int compare(int a[],int i,int j,int p)
{
 if(a[j]<=a[i]*p)
 return j-i+1;
 else
 {  
 int m=compare(a,i+1,j,p);
 int n=compare(a,i,j-1,p);
 return m>n?m:n;
    }
 
}
int main()
{
 int n,p;
 scanf("%d %d",&n,&p);
 register int i,j;
 int a[n];
 for(i=0;i<n;i++)
 {
  scanf("%d",a+i);  
 }
 qsort(a,n,sizeof(int),cmp);
  
 printf("%d\n",compare(a,0,n-1,p));
 
 
   return 0;
}


 
上面的那个版本看似很整洁,一个是超时,不用说了,肯定是很多个地方算重复了,可以优化,
那错误在哪里,实质上在数据范围,没错他们都在整形的范围内,但是你中间可是要乘法的啊,
你一乘就溢出了,所以要用到long long 类型才可以。。解决了一个错误,我们来关注超时
 
 
#include<stdio.h>      //错误版本二。
#include<stdlib.h>
int cmp(const void *a,const void *b)
{
 return *(int *)a-*(int *)b;
 
}
int main()
{
 int n,p;
 scanf("%d %d",&n,&p);
 register int i,j;
 int a[n];
 for(i=0;i<n;i++)
 {
  scanf("%d",a+i);  
 }
 qsort(a,n,sizeof(int),cmp);
 int max=0;
    long long m,q;
 for(i=0;i<n;i++)     //逆这找  超时  
 {
  if(n-i<=max)
  break;
  for(j=n-1;j>=i;j--)
  {
     if(j-i+1<=max)
      break;
   m=a[j];
   q=a[i];
   q=q*p;
   if(m<=q)
   {
   max=j-i+1;
   break;
      }
  }
 }
 
 
 
 
 printf("%d\n",max);
 
 
   return 0;
}
 
 
这时我想递归既然超时了,那我就改成循环,做了一些优化,比如明明不用继续下去的就跳出循环结束。。
结果还是超时。。。错在哪里了呢。。。  哦 我想清楚了,我是从后面往前找的,我已经排完序了,
如果从后面往前找的话 ,不具备继承关系,下一次还得从最后开始一个一个试。。虽有有优化但不足。
我们改成前面去找,这样就具备继承关系
 
 
 
#include<stdio.h>                       //正确版本一
#include<stdlib.h>
int cmp(const void *a,const void *b)
{
 return *(int *)a-*(int *)b;
 
}
int main()
{
 int n,p;
 scanf("%d %d",&n,&p);
 register int i,j;
 int a[n];
 for(i=0;i<n;i++)
 {
  scanf("%d",a+i);  
 }
 qsort(a,n,sizeof(int),cmp);
 int max=0;
    long long m,q;
   j=0;
    for(i=0;i<n;i++)   
  {
  if(n-i<=max)
  break;
  for(;j<n;j++)
  {
   
   m=a[j];
   q=a[i];
   q=q*p;
   if(m<=q)
   {
   if(j-i+1>max)
   max=j-i+1;
      }
      else
   {
    break;
   }
  }
 }
 
 
 printf("%d\n",max);
 
 
   return 0;
}
 
 
这时我要想既然我开始的时候都排序了,那我们可不可以用二分呢,当然是可以的了。。 
 
 
#include<stdio.h>                           //正确版本二

#include<stdlib.h>

int cmp(const void *a,const void *b)

{

 return *(int *)a-*(int *)b;

 

}
int erfen(int a[],int t,int low,int high,int p)

{

 int mid;

 long long m,q;

 m=t;

 int tem_low=low,tem_high=high;

 while(low<=high)

 {

 mid=(low+high)/2;

 q=a[mid]; 

 if(m*p>=q)

 {

  low=mid+1;

  

 }

 else

 {

  high=mid-1;

 }

   }

   return high; 

 }

int main()

{

 int n,p;

 scanf("%d %d",&n,&p);

 register int i,j;

 int a[n];

 for(i=0;i<n;i++)

 {

  scanf("%d",a+i);  

 }

 qsort(a,n,sizeof(int),cmp);

 int max=0; 

 int temp;

 

 int m=0;

 for(i=0;i<n;i++)

 {

  if(n-i<=max)

  break;

  j=n-1;

  m=erfen(a,a[i],m,j,p);

  if(m-i+1>max)

  max=m-i+1;

  

 }
 

 

 printf("%d\n",max);
 

 

   return 0;

}

 

1030 完美数列 (25分)

标签:nba   二分   void   sub   gis   font   str   scanf   版本   

原文地址:https://www.cnblogs.com/bigageyuan/p/13903885.html

版权声明:完美者 发表于 2020-10-31 2:20:23。
转载请注明:1030 完美数列 (25分) | 完美导航

暂无评论

暂无评论...