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