文章目录
一【题目难度】
- 乙级
二【题目编号】
- 1030 完美数列 (25 分)
三【题目描述】
- 给定一个正整数数列，和正整数 p p p，设这个数列中的最大值是 M M M，最小值是 m m m，如果 M ≤ m p M≤mp M≤mp，则称这个数列是完美数列。
- 现在给定参数 p p p 和一些正整数，请你从中选择尽可能多的数构成一个完美数列。
四【题目示例】
-
输入格式：
输入第一行给出两个正整数 N N N 和 p p p，其中 N （ ≤ 1 0 5 ） N（≤10^5 ） N（≤105）是输入的正整数的个数， p （ ≤ 1 0 9 ） p（≤10^9 ） p（≤109）是给定的参数。第二行给出 N N N 个正整数，每个数不超过 1 0 9 10^9 109 。 -
输出格式：
在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。 -
输入样例：
10 8
2 3 20 4 5 1 6 7 8 9 -
输出样例：
8
五【解题思路】
- 这道题的重点是理解好题意，题目的意思是给你一些数字，让你从这里找出最大 M M M的和最小的 m m m，使其满足 M ≤ m p M≤mp M≤mp，并且还要求整个结果数组达到最长，既然这样，对这一系列数字进行排序再找出最大最小比较好，所以首先对其按照从小到大排序，然后再逐一根据题目条件搜索，但是如果采用 O ( N 2 ) O(N^2) O(N2)的循环搜索肯定会超时，所以既然有序，首先想到二分法，这个判断条件就是 M > m p M>mp M>mp，这时前一个就是满足题目要求最长的（因为数组已经有序），其后面的肯定都不符合要求，其次还要注意，结果最少都是1，因为最少有一个满足要求，所以每次更新找最大的即可
六【最终得分】
- 25分
七【代码实现】
#include<stdio.h>
#include<stdlib.h>
int max_1030_PerfectSequence(int a,int b)
{
return a > b ? a : b;
}
int cmp_1030_PerfectSequence(const void *a,const void *b)
{
return *(int *)a > *(int *)b ? 1 : -1;
}
int binarySearch(int* nums,int i,int n,long long mp)
{
if(nums[n-1] < mp)
{
return n;
}
int left = i + 1;
int right = n - 1;
while(left < right)
{
int mid = (left +right) / 2;
if(nums[mid] <= mp)
{
left = mid + 1;
}
else
{
right = mid;
}
}
return left;
}
int main()
{
int n,p,res = 1;
scanf("%d %d",&n,&p);
int* nums = (int *)calloc(n,sizeof(int));
for(int i = 0;i<n;i++)
{
scanf("%d",&nums[i]);
}
qsort(nums,n,sizeof(int),cmp_1030_PerfectSequence);
for(int i = 0;i<n;i++)
{
int index = binarySearch(nums,i,n,(long long)nums[i] * p);
res = max_1030_PerfectSequence(res,index - i);
}
printf("%d",res);
return 0;
}