首页 > 其他分享 >PAT Basic 1030. 完美数列

PAT Basic 1030. 完美数列

时间:2023-03-16 20:44:47浏览次数:43  
标签:10 PAT 数列 int long ptInt Basic 1030 sizeof

PAT Basic 1030. 完美数列

1. 题目描述:

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

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

2. 输入格式:

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

3. 输出格式:

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

4. 输入样例:

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

5. 输出样例:

8

6. 性能要求:

Code Size Limit
16 KB
Time Limit
200 ms
Memory Limit
64 MB

思路:

这道题应该是我前40题中印象最深刻的一道,因为我觉得自己思路没问题,但就是不能AC,卡到第二天才找到的bug。。。

我当时的思路很直接,题目要求从给定的数列中选择尽可能多的数构成完美数列,那么就首先对给定数列进行排序,然后根据判断条件\(M \le mp\)删去最大值或最小值,直到条件被满足。因为想留下尽可能多的数字,所以就要使得删减后的\(M/m\)尽可能多的减少,直到\(\le p\),有点贪心的思想。这里存储\(\le 10^9\)的数字用int类型(4字节)即可,但是涉及到两个数字的乘积\(\le 10^{18}\),所以最终需要用long类型(8字节)。

这里我一开始不能AC的原因就是ptInt[j]*ptInt[i] == ptInt[i+1]*ptInt[j-1]的处理有问题,排序后两端的最大最小值都可能存在多个重复值,遇到这种情况时要选择最大最小值的较小重复次数进行删减。。。

My Code:

#include <stdio.h>
#include <stdlib.h>

int cmp(const void * a, const void * b)
{
    //int * left = (int *)a;
    //int * right = (int *)b;
    long * left = (long *)a;
    long * right = (long *)b;
    return *left - *right;
}

int main(void)
{
    int number = 0, factor = 0;
    //int * ptInt;
    long * ptInt; //first submit testpoint5 reject, for (int*int) may overflow int's range.
    int i, j;
    int countI = 0, countJ = 0; //for testpoint4
    
    scanf("%d%d", &number, &factor);
    
    //ptInt = (int *)malloc(sizeof(int) * number);
    ptInt = (long *)malloc(sizeof(long) * number);
    for(i=0; i<number; i++)
    {
        scanf("%ld", &ptInt[i]);
    }
    
    qsort(ptInt, number, sizeof(long), cmp); // sort the sequence from small to big
    
//     for(i=0; i<number; i++)
//     {
//         printf("%d ", ptInt[i]);
//     }
//     printf("\n");
    
    i = 0;
    j = number - 1;
    
// //     10 8
// //     1 1 1 1 8 8 8 9 9 9 
//     while(ptInt[j] > factor * ptInt[i]) //testpoint4 reject like above example, this method exist bug
//     {
//         if(ptInt[j]*ptInt[i] < ptInt[i+1]*ptInt[j-1]) // j / i+1 < j-1 / i
//         {
//             i++;
//         }
//         else
//         {
//             j--;
//         }
//     }
    
    while(ptInt[j] > factor * ptInt[i]) //fixed this bug!!!
    {
        countI = 1;
        countJ = 1;
        
        if(ptInt[j]*ptInt[i] < ptInt[i+1]*ptInt[j-1]) // j / i+1 < j-1 / i
        {
            i++;
        }
        else if(ptInt[j]*ptInt[i] > ptInt[i+1]*ptInt[j-1])
        {
            j--;
        }
        else // important!!! ptInt[j]*ptInt[i] == ptInt[i+1]*ptInt[j-1]
        {
            while(ptInt[i] == ptInt[i+countI])
                countI++;
            while(ptInt[j] == ptInt[j-countJ])
                countJ++;
            
            if(countI > countJ)
                j -= countJ;
            else
                i += countI;
        }
    }
    
    printf("%d\n", j-i+1);
    
//     printf("sizeof(int): %zd\n", sizeof(int));
//     printf("sizeof(long): %zd\n", sizeof(long));
    
    free(ptInt);
    return 0;
}


// #include<stdio.h>
// #include<stdlib.h>
// //快排
// int compare(const void *a,const void *b)
// {
//     if(*(long *)a>*(long *)b)
//         return 1;
//     else if(*(long *)a<*(long *)b)
//         return -1;
//     else
//         return 0;
// }
// int main()
// {
//     long *num,*nums;
//     int n,p;
//     register int i,j,max=1;
//     scanf("%d%d",&n,&p);
//     num=(long *)malloc(n*sizeof(long));
//     nums=(long *)malloc(n*sizeof(long));
//     for(i=0;i<n;i++)
//     {
//         scanf("%ld",num+i);
//     }
//     qsort(num,n,sizeof(long),compare);
//     for(i=0;i<n;i++)
//     {
//         nums[i]=num[i]*p;
//     }
//     for(i=0;i<n;i++)
//     {
//         if(i+max>n)
//             break;
//         for(j=i+max;j<n;j++)
//         {
//             if(nums[i]>=num[j])
//             {
//                 if(max<j-i+1)
//                 {
//                     max=j-i+1;
//                 }
//             }
//             else
//             {
//                 break;
//             }
//         }
//     }
//     printf("%d\n",max);
// }

标签:10,PAT,数列,int,long,ptInt,Basic,1030,sizeof
From: https://www.cnblogs.com/tacticKing/p/17224059.html

相关文章

  • PAT Basic 1029. 旧键盘
    PATBasic1029.旧键盘1.题目描述:旧键盘上坏了几个键,于是在敲一段文字的时候,对应的字符就不会出现。现在给出应该输入的一段文字、以及实际被输入的文字,请你列出肯定坏......
  • vuex TypeError: Cannot read properties of undefined (reading ‘dispatch‘)
      1、入口文件main.js  2、或者版本不匹配 vue2安装3版本的vuex,默认安装的4版本给vue3用//卸载原来安装的vuexnpmuninstallvuex//安装3.6.2版本的vuexnpm......
  • 使用patch-package定制node_modules 中的依赖包
    背景:首先,需求是这样,Vue项目中使用的是iview第三方UI库,要修改组件DatePicker中默认选中的当日的日期(如下图),实现无论在哪个时区,均显示中国的日期   由于,iview提供的a......
  • singleton pattern
    C1.overviewp1.conceptproblemsPeoplecanusereflectmechanismtocreateotherinstancetoviolatesingleton.ThesafetyofthreadInstructionreordering......
  • diff 命令 , patch
    关于diff命令:      接下来看合并:    关于Patch  ......
  • 解决 The bean 'xxx', defined in class path resource [], could not be registered.
    问题:在实现短信发送拦截功能时,创建了PassportInterceptor验证码拦截器类,使用了@Conponent注解;同时创建了InterceptorConfig拦截器配置类,使用了@Conponent注解,并使用@......
  • spingboot-context-path-默认值以及配置
    springboot项目的context-path的默认值:/可以在application.yml配置文件中自行配置:SpringBoot2.0.0.RELEASE版本以及之后server:port:80servlet:context-path:......
  • 爬虫入门--xpatch
    XPath是一门在XML文档中查找信息的语言。XPath使用路径表达式在XML文档中进行导航。XPath包含一个标准函数库。XPath是XSLT中的主要元素。XPath是一个W3C......
  • 10 url-pattern的匹配规则
    ​ URL的匹配规则精确匹配精确匹配是指<url-pattern>中配置的值必须与url完全精确匹配。<servlet-mapping><servlet-name>demoServlet</servlet-name><......
  • 10 url-pattern的匹配规则
    ​ URL的匹配规则精确匹配精确匹配是指<url-pattern>中配置的值必须与url完全精确匹配。<servlet-mapping><servlet-name>demoServlet</servlet-name><......