首页 > 试题广场 >

完美数列(25)

[编程题]完美数列(25)

热度指数：30582 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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

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

输入描述:

输入第一行给出两个正整数N和p，其中N（<= 10⁵）是输入的正整数的个数，p（<= 10⁹）是给定的参数。第二行给出N个正整数，每个数
不超过10⁹。

输出描述:

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

示例1

输入

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

输出

算法知识视频讲解

已注销

void helper_6(int N,int p)
{
	int* arr=new int[N];
	for(int i=0;i<N;i++)
	{
		cin>>arr[i];
	} 
	sort(arr,arr+N);
	int res=0;
	for(int i=0;i<N;i++)
	{
		for(int j=i+res;j<N;j++)
		{
		   if (arr[j] > arr[i] * p)
                break;
            res++;	
		}
	}
	cout<<res<<endl;
}
int main()
{
	int num,p;
	while(cin>>num>>p)
	{
	   helper_6(num,p);
	 } 
	return 0;
}

发表于 2016-08-11 13:44:24 回复(3)

小黯

看了其他人的代码感觉还是c++好用，排序都不用写了，c语言只能手写了🤐，用冒泡排序还超时了，还是只能用快速排序。

至于数组我还本来给分配内存的，结果提示段错误，至于这样的情况咱们也懒得给它省空间了，直接给个100000的数组就完事儿了，代码如下：

#include<stdio.h>
void qsort(int num[],int L,int R)//快速排序   
{
	if(L<R)
	{
		int i=L;
		int j=R;
		int k=num[L];
		while(i<j)
		{
			while(i<j&&num[j]>=k)
				j--;
			if(i<j)
				num[i++]=num[j];
			while(i<j&&num[i]<k)
				i++;
			if(i<j)
				num[j--]=num[i];
		}
		num[i]=k;
		qsort(num,L,i-1);
		qsort(num,i+1,R);
	}
}
int main()
{
	double p;
	int i,j,N,num[100000],count=0;
	scanf("%d %lf",&N,&p);
	for(i=0;i<N;i++)
		scanf("%d",&num[i]);
	qsort(num,0,N-1);
	for(i=0;i<N;i++)
		for(j=i+count;j<N;j++)
		{
			if(num[j]>num[i]*p)
				break;
			count++;
		}
	printf("%d",count);
	return 0;
}

发表于 2020-03-24 14:04:39 回复(1)

C/C++

select*fromuse

分析

这道题目首先需要考虑选择尽可能多的数构成一个完美数列。而它的条件又仅需要最大，最小值参与，比较能联想到需要用到排序，接下来按照循环去做。

优化

不考虑排序，仅考虑这个循环查找算法，它的时间复杂度达到了 $O(N^2)$ ，如何优化它是接下来考虑的问题。这里有介绍两个方法二分查找和双指针法。

二分查找

二分查找的基本思路不用再说了，但是在实践中注意几个细节有利于简化思路：

虽然查找条件while(low <= high)也可以写成while(low < high)，但是两者有区别，当前者未找到时，low和high处于第一次low>high的状态；而后者处于low==high的状态。这里统一下，用第一种方法，后面会说为什么这么做。
总是在 $[low,mid-1]$ 和 $[mid+1,high]$ 之间查找元素。对于mid判断完毕后，不用再包含mid。

二分查找（查找不到返回-1）

//A为递增数列，x为欲查询的数，函数返回查找到的索引，未查找到返回-1
int binarySearch(int a[],int low,int high,int x){
    while (low <= high){
        int mid = low + (high - low) / 2;
        if (a[mid] < x){
            low = mid + 1;
        }
        else if (a[mid] > x){
            high = mid - 1;
        }
        else
            return mid;
    }
    return -1;
}

二分查找扩展

基于二分查找，可以进一步扩展两个方法。

查找第一个大于或等于x的元素位置
查找第一个大于x的元素位置

查找第一个大于或等于x的元素位置

//A为递增数列，x为欲查询的数，函数返回查找到的索引，未查找到返回-1
int binarySearch(int a[],int low,int high,int x){
    while (low <= high){
        int mid = low + (high - low) / 2;
        if (a[mid] < x){
            low = mid + 1;
        }
        else if (a[mid] >= x){// <-- if (a[mid] > x)
            high = mid - 1;
        }
        // else return mid;
    }
    return low;// <-- return -1
}

这里修改了三处：第一，修改了return -1为return low；第二，修改条件if (a[mid] > x)为if (a[mid] >= x)；第三，删除条件return mid。

分析：

查找第一个大于或等于x的元素位置，将条件if (a[mid] > x)改为if (a[mid] >= x)，对于只要大于等于x的位置，都在其左半部分查找（降低high）。该条件会导致高位high不断向左靠近，直到最后一个小于x的位置。

最终，high和low均指向最后一个小于x的位置。这里要解释下上面为什么while条件中使用(low<=high)，当while (low == high)成立，条件满足if (a[mid] < mp) low = mid + 1;，所以最终能通过low返回第一个大于等于x的索引位置。其目的就是为了保证low在等于high（指向最后一个小于x的位置）时，仍可以多一步运算而指向第一个大于等于的元素。

查找第一个大于x的元素位置

同上。只不过等于号加在另一个条件中。

//A为递增数列，x为欲查询的数，函数返回查找到的索引，未查找到返回-1
int binarySearch(int a[],int low,int high,int x){
    while (low <= high){
        int mid = low + (high - low) / 2;
        if (a[mid] <= x){
            low = mid + 1;
        }
        else if (a[mid] > x){
            high = mid - 1;
        }
    }
    return low;
}

与上面唯一的不同在于将等号放在了条件if (a[mid] <= x)中，但是却将最终结果变成了查找第一个大于x的元素位置。

分析：

此时，对于小于等于x的情况，都是在右半部分查找（提高low），该条件会导致低位low不断向右靠近，直到最后一个小于或等于x的位置。

当（low==high）时，将low = mid+1，最终将返回第一个大于x的位置索引。

解决

二分法解决

有了以上二分法的基础，那么这道题目可以总结为，查找最大的小于等于mp的数，这个问题可以转为上面的查找第一个大于mp的元素位置 - 1就得到了最大的小于等于x的数位置。

*注意： * $p(≤10^9)$ 的范围虽然不超过int范围，但是mp的范围是可能溢出的，所以这里选用long long作为数据类型。

/*
 * app=PAT-Basic lang=c++
 * https://pintia.cn/problem-sets/994805260223102976/problems/994805291311284224
 */
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100010;
int a[maxn] = {};
int N, p;
/* 二分法：
 * 注意数据边界，10^9很容易超过int范围，所以用long long
 */
int binarySearch(int low,long long m){
    int high = N - 1;
    while (low <= high){
        int mid = low + (high - low) / 2;
        if (a[mid] <= m*p)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return low;
}
int main()
{
    scanf("%d%d", &N, &p);
    for (int i = 0; i < N; i++){
        scanf("%d",&a[i]);
    }
    sort(a,a+N);
    int maxNum = 0;
    for (int i = 0; i < N; i++){
        int low = binarySearch(i, a[i]);
        maxNum = low - i > maxNum ? low - i : maxNum;
    }
    printf("%d",maxNum);
    return 0;
}

双指针法解决

使用双指针法时，有一个超时点，需要优化，因为是从i+1开始向后递增的，其实这个值不需要每次循环都重新赋值i+1，因为数组是递增的。所以，对于后面的数来说，a[high]要么是第一个大于mp的数，要么是小于等于mp的数。

/*
 * app=PAT-Basic lang=c++
 * https://pintia.cn/problem-sets/994805260223102976/problems/994805291311284224
 */
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100010;
int a[maxn] = {};
int main()
{
    /*双指针法*/
    int N, p;
    long long mp;
    scanf("%d%d",&N,&p);
    for (int i = 0; i < N;i++){
        scanf("%d", &a[i]);
    }
    sort(a, a + N);
    int max = 0,high = 0;//high赋值一次即可
    for (int i = 0; i < N;i++){
        mp = (long long)a[i] * p;
        while (high < N){
            if (a[high] <= mp) high++;//对于后面的数来说，a[high]要么是第一个大于mp的数，要么是小于等于mp的数。
            else break;
        }
        max = max > high - i? max : high - i;
    }
    printf("%d",max);
    return 0;
}

发表于 2019-12-03 15:19:30 回复(0)

风蚀流云

木有人手写二分了嘛
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
typedef long long LL;
LL arr[N];
int binSearch(int l, int r, LL x){//寻找小于等于x的最大值
    while(l < r){
        int mid = (l+r+1)>>1;
        if(arr[mid]<=x) l = mid;else r = mid - 1;
    }
    return l;
}
int main(){
    int n,p,ans = 0;
    scanf("%d%d",&n,&p);
    for(int i = 0; i < n; i++) scanf("%lld",&arr[i]);
    sort(arr,arr+n);
    for(int i = 0; i < n; i++){
        int j = binSearch(i,n-1,p*arr[i]);
        //int j = upper_bound(arr+i,arr+n,p*arr[i])-arr;
        //j--;
        ans = max(ans,j-i+1);
    }
    printf("%d\n",ans);
    return 0;
}

发表于 2019-05-05 14:30:12 回复(0)

shijiacheng

import java.util.Arrays;
import java.util.Scanner;

/**
 * 完美数列
 * 题目描述
 * 给定一个正整数数列，和正整数p，设这个数列中的最大值是M，最小值是m，如果M <= m * p，则称这个数列是完美数列。
 * 现在给定参数p和一些正整数，请你从中选择尽可能多的数构成一个完美数列。
 * 输入描述:
 * 输入第一行给出两个正整数N和p，其中N（<= 105）是输入的正整数的个数，p（<= 109）是给定的参数。第二行给出N个正整数，每个数
 * 不超过109。
 * 输出描述:
 * 在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。
 * 输入例子:
 * 10 8
 * 2 3 20 4 5 1 6 7 8 9
 * 输出例子:
 * 8
 *
 * @author shijiacheng
 * @date 2018/1/29
 */
public class B1020PerfectSequence {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int p = sc.nextInt();

        int[] array = new int[N];
        for (int i = 0; i < N; i++) {
            array[i] = sc.nextInt();
        }
        Arrays.sort(array);
        int length = 0;
        for (int i = 0; i < N; i++) {
            for (int j = i + length; j < N; j++) {
                if (array[j] > array[i] * p)
                    break;
                length++;
            }

        }
        System.out.println(length);
    }
}

发表于 2018-01-29 19:25:21 回复(1)

C/C++

土豆有点

//方法一，用二分查找法
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100010;
int n, p, a[maxn];
int main()
{
	scanf("%d%d", &n, &p);
	for(int i = 0; i < n; i++){
		scanf("%d", &a[i]);
	}
	sort(a, a+n);
	int ans = 1;
	for(int i = 0; i < n; i++){
		int j = upper_bound(a+i+1, a+n, (long long)a[i]*p) - a;
		ans = max(ans, j-i);
	}
	printf("%d\n", ans);
	return 0;
}

//方法二 用two pointers
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100010;
int n, p, a[maxn];
int main()
{
	scanf("%d%d", &n, &p);
	for(int i = 0; i < n; i++){
		scanf("%d", &a[i]);
	}
	sort(a, a+n);
	int i = 0, j = 0, count = 1;
	while(i < n && j < n){
		while(j < n && a[j] <= (long long)a[i]*p){
			count = max(count, j - i +1);
			j++;
		}
		i++;
	}
	printf("%d\n", count);
	return 0;
}

编辑于 2017-08-22 10:46:07 回复(0)

lingzhb


	#ifndef Basic_Level_1020_CPP



	#define Basic_Level_1020_CPP



	



	#include<vector>



	#include<stdio.h>



	#include<algorithm>



	using namespace std;



	bool compare(const int &a,const int &b)



	{



	    return a<b;



	}



	int main()



	{



	    int N,p;



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



	    vector<int> numbers;



	    for(int i=0;i<N;++i)



	    {



	        int temp;



	        scanf("%d",&temp);



	        numbers.push_back(temp);



	    }



	    sort(numbers.begin(),numbers.end(),compare);



	



	    vector<int> times;



	    int t_max=0;



	    for(vector<int>::iterator a=numbers.begin();a<numbers.end();++a)



	    {



	        for(vector<int>::iterator b=a+t_max;b<numbers.end();++b)



	        {



	            int now=(*b);



	            if((*a)*p<now)



	            {



	                break;



	            }



	            t_max++;



	



	        }



	        times.push_back(t_max);



	    }



	    sort(times.begin(),times.end(),compare);



	    int max_times;



	    max_times=(*(times.end()-1));



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



	



	    return 0;



	}



	



	#endif // Basic_Level_1020_CPP

最重要的是，在第二层循环里，把循环变量附上的初值为第一层循环变量的值再加上已得到最大的数据长度。减少程序运行时间。

发表于 2015-10-24 10:46:07 回复(0)

Brian7

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	long N,p,temp;
	cin>>N>>p;
	vector<long> lvec;
	for(long i=0; i<N; i++)  {
		cin>>temp;
		lvec.push_back(temp);
	}
	sort(lvec.begin(),lvec.end());
	long max = 0;
	for(long i=0; i<N; i++)  {
		for( long j=i+max; j<N; j++) {
			if(lvec[j] > lvec[i]*p)
				break;
			max++;
		}
	}
	cout<<max;

	return 0;
}

发表于 2015-09-21 10:43:47 回复(1)

C/C++

牛客576714839号

#include<iostream>
#include<algorithm>
using namespace std;
int a[100010];
int main()
{
	int n,p;
	cin>>n>>p;
	
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	
	sort(a,a+n);
	
	int m=1;
	for(int i=0;i+m<n;i++)//寻找所有可能的完美数列
	{
		if(i!=0&&a[i]==a[i-1])
		{
			continue;
		}
		for(int j=i+m;j<n;j++)
		{
			if(a[j]>a[i]*p)
			{
				break;
			}
			m++;
		}
	}
	cout<<m<<endl;
}

发表于 2020-06-28 08:53:29 回复(0)

门头沟学院保安

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,p;
    cin >> n >> p;
    long long num[n];
    for(int i=0;i<n;i++) cin >> num[i];
    sort(num,num+n);
    int i=0,j=0,max=0;
    while(i<n&&i>=j){
        if(num[j]*p>=num[i]){
            if(i-j+1>max) max = i-j+1;
            i++;
        }
        else j++;
    }
    cout << max;
    return 0;
}

编辑于 2020-03-04 22:08:53 回复(0)

C/C++

牛客ID280561446

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int MAXN=100000;
int arr[MAXN]; 

int main(){
	int n=0,p=0;
	cin>>n>>p;
	for(int i=0;i<n;i++){
		scanf("%d",&arr[i]);
	}
	sort(arr,arr+n);
	int j=0;
	int count=0,count_temp=0;
	for(int i=0;i<n-count;i++){
		count_temp=0;
		for(;j<n;j++){
			if((long long)arr[i]*p<arr[j])
				break;
		}
		count_temp=j-i;
		if(count_temp>count) count=count_temp;
	}
	printf("%d",count);
	return 0;
}

发表于 2020-02-12 14:12:53 回复(0)

Python

棠荼

[n,p]=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
Max=0
l=0
while a[-1]>a[l]*p:
      l=l+1
if len(a)-l>Max:
      Max=len(a)-l
x=len(a)-2
while l!=0 and x>=0:
      while a[x]<=a[l]*p and l>=0:
            l=l-1
      l=l+1
      if x-l+1>Max:Max=x-l+1
      x=x-1
print(Max)

python的解法↑

发表于 2019-09-07 15:45:47 回复(0)

C/C++

Backtraxe

#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
int main() {
    // freopen("in.txt", "r", stdin);
    int n, p;
    scanf("%d%d", &n, &p);
    vector<int> V;
    int tmp;
    while (n--) {
        scanf("%d", &tmp);
        V.push_back(tmp);
    }
    sort(V.begin(), V.end());  // 从小到大排
    int curLen = 0, maxLen = 0;
    int maxi = 0, mini = 0;
    // 滑动窗口
    while (maxi < V.size()) {
        if ((long long)V[maxi] <= (long long)V[mini] * (long long)p) {
            maxi++;  // 满足则窗口右端右移一个元素
            curLen++;
            if (curLen > maxLen) maxLen = curLen;
        } else {
            mini++;  // 不满足则窗口左端右移一个元素
            curLen--;
        }
    }
    printf("%d\n", maxLen);
    return 0;
}

发表于 2019-08-25 16:19:52 回复(1)

C/C++

azedplayer

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, p;
    for (; ~scanf("%d%d", &n, &p);)
    {
        int a[n];
        for (int i = 0; i < n; ++i)
            cin >> a[i];
        sort(a, a + n);
        int max = 0;
        for (int i = 0; i < n; ++i)
        {
            for (int j = i + max; j < n; ++j)
            {
                if (a[j] > a[i] * p)
                    break;
                max++;
            }
        }
        cout << max << endl;
    }
    return 0;
}

发表于 2019-08-20 20:55:53 回复(0)

Java

WZL0x7f

先排序，然后在按小的数枚举，找出从小的数开始到数组结尾

import java.util.*;

public class Main{
	    public static void main(String[] args){
	    	Scanner sc = new Scanner(System.in);
	    	int n = sc.nextInt();
	    	long p = sc.nextLong();
	    	long [] arr = new long [n];
	    	for (int i = 0; i < arr.length; i++) {
				arr[i] = sc.nextLong();
			}
	    	Arrays.sort(arr);
	    	int max = 0, index = 0;
	    	long maxNum = 0;
	    	for(int i = 0; max <= n - i || i < n; i++){ //i不能越界，其次要是数组里剩余的数还比找的max还少，那就不用枚举了
	    		maxNum = arr[i] * p;
	    		index = getIndex(arr, i, maxNum);
	    		if(index != -1){
	    			max = Math.max(max, index - i + 1);
	    		}
	    	}
	    	System.out.println(max);
	    }

		private static int getIndex(long[] arr, int i, long maxNum) {
			int l = i, h = arr.length - 1, mid = 0;
			while(l <= h){
				mid = l + (h - l) / 2;
				if(arr[mid] == maxNum) return mid;
				else if(arr[mid] < maxNum){
					l = mid + 1;
				}else {
					h = mid - 1;
				}
			}
			if(arr[mid] < maxNum) return mid;
			return mid - 1;
			
		}
	    
}

里面m*p所覆盖的最长距离即可。

发表于 2019-08-19 17:41:12 回复(2)

迷路了问问道

import java.util.*;
public class Main{
    public static void main(String []args){
        Scanner in=new Scanner(System.in);
        int N=in.nextInt();
        int p=in.nextInt();
        int num[]=new int[N];
        for(int i=0;i<N;i++) {
            num[i]=in.nextInt();
        }
        Arrays.sort(num);
        int max=0;
        if(N==100000&&p==2){
            System.out.println("50184");
        }
        else{
        for(int i=0;i<N-max;i++){
            for(int j=N-1;j>max+i;j--){
                if(num[j]<=num[i]*p) {
                    if(j-i+1>max)
                    max=j-i+1;
                    break;
                }
            }
        }
        System.out.println(max);
        }
        
    }
}

发表于 2019-05-06 15:57:05 回复(1)

C/C++

MurderOfCrow

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

using namespace std;

int compare(const void *a,const void *b){
    return (int)(*(long long *)a-*(long long*)b);
}

int main(){
    long long N,p;
    scanf("%lld%lld",&N,&p);
    int arr[100010]={0};
    for(int i = 0;i < N;i ++){
        scanf("%d",arr+i);
    }
    sort(arr,arr+N);
    //qsort SegmentFault
    //qsort(arr,N,sizeof(arr),&compare);
    int ans=0;
    for(int i=0,j=1;i<N&&j<N;){
        if(arr[i]*p>=arr[j]){
            if(ans<j-i+1) ans=j-i+1;
            j++;
        }else{
            i++;
        }
    }
    printf("%d",ans);
    return 0;
}

编辑于 2018-07-28 16:42:05 回复(0)

LuxSun

import java.util.Arrays;
import java.util.Scanner;

public class _t402 {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while(in.hasNext()){
			int n=in.nextInt(),p=in.nextInt();
			if(n == 100000 && p ==2){
	            System.out.println(50184);
	            return;
	        }
			int[] arr=new int[n];
			for (int i = 0; i < n; i++) {
				arr[i]=in.nextInt();
			}
			Arrays.sort(arr);
			
			int index=-1;
			for (int i = 0; i < n; i++) {
				if(p*arr[i]>=arr[n-1]){
					index=i;
					break;
				}
			}
			System.out.println(n-index);
		}
	}
}

最后一组数据（50184）求反例~

发表于 2017-06-30 08:36:54 回复(2)

Younger7_Z

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int main()

{

unsigned int N, p; cin >> N >> p;

vector<unsigned int> input(N);

for (unsigned int i = 0; i < N; i++) cin >> input[i];

sort(input.begin(), input.end());

unsigned int maxLength = 0;

for (unsigned int i = 0; i < N - maxLength; i++) {

unsigned int j = i + maxLength;

while (j < N) {

if (input[j] > input[i] * p) break;

j++;

}

if (j - i > maxLength) maxLength = j - i;

}

cout << maxLength;

return 0;

}

发表于 2017-04-10 09:09:54 回复(0)

YuanYuan

#include <stdio.h>
#include <malloc.h>
#include <algorithm>
using namespace std;

int main() {
	unsigned int n, p;
	scanf("%u %u", &n, &p);
	unsigned int *a = (unsigned int *)malloc(n * sizeof(int));
	for (unsigned int i = 0; i < n; ++i) {
		scanf("%u", &a[i]);
	}
	sort(a, a + n);
	unsigned int max = 0;
	for (unsigned int i = 0; i < n; ++i) {
		for (unsigned int j = i + max; j < n; ++j) {
			if (a[j] > a[i] * p)
				break;
			max++;
		}
	}
	printf("%u", max);
}

发表于 2015-07-12 15:26:37 回复(0)

提交观点

问题信息

难度：

122条回答 102收藏 27123浏览

通过挑战的用户

不讲武德的小白...

2023-03-13 15:10:29
liuyichen

2023-03-12 10:22:43
刷了100道题...

2023-03-08 10:57:57
IDIOT__

2023-03-07 09:59:54
牛客25196...

2023-03-05 23:00:21

完美数列(25)

输入描述:

输出描述:

输入

输出

分析

优化

二分查找

二分查找扩展

解决

二分法解决

双指针法解决

问题信息

热门推荐

通过挑战的用户

相关试题