首页 > 试题广场 >

完美数列(25)

[编程题]完美数列(25)
  • 热度指数：30923 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
给定一个正整数数列，和正整数p，设这个数列中的最大值是M，最小值是m，如果M <= m * p，则称这个数列是完美数列。



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

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


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

输入

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

输出

8
算法知识视频讲解
添加回答
C/C++
select*fromuse头像 select*fromuse

分析

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

优化

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

二分查找

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

  • 虽然查找条件while(low <= high)也可以写成while(low < high)，但是两者有区别，当前者未找到时，low和high处于第一次low>high的状态；而后者处于low==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的数位置。

*注意： *的范围虽然不超过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头像 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头像 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头像 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号头像 牛客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头像 牛客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头像 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头像 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头像 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头像 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头像 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头像 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头像 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)
C/C++
练习时长两年半的Java练习生头像 练习时长两年半的Java练习生 
#include<stdio.h>
#include<stdlib.h>
int c(const void*a,const void*b){return*(int*)a-*(int*)b;}
int main (){//the shorter,the better.
    int i,j,n,p,m,*a;
    for(;~scanf("%d%d",&n,&p);free(a),printf("%d\n",m)){
       for (a = (int*) malloc(sizeof(int)*n),i=0;i<n&&~scanf("%d",&a[i]);i++);
       for (qsort(a,n,sizeof(int),c),m=i=0;i<n;i++) for (j=i+m;j<n&&a[j]<=a[i]*p;++m,++j);
    }
}

发表于 2018-02-01 15:36:43 回复(0)
C/C++
Myhui头像 Myhui 
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    int j,n;long long p,s[100010];
    cin>>n>>p;
    for(int i=0;i<n;i++)
        cin>>s[i];
    sort(s,s+n);
    int sum=1;                          //因为p是正整数，所以至少有一个数符合max<=min*p
    for(int i=0;i<n;i++){
        long long x=s[i]*p;             //每次循环s[i]即为min
        j=upper_bound(s+i+1,s+n,x)-s;   //从s[i+1]到s[n-1]中查找第一个大于s[i]*p的数的(upper_bound()函数只是返回地址，还要减去初始地址即数组名得到元素下标)
        sum=max(sum,j-i);               //每次循环都要更新最大长度
    }
    cout<<sum;
    return 0;
}

发表于 2018-02-01 00:30:42 回复(0)
提交观点

问题信息

难度：
123条回答 27773浏览

热门推荐

通过挑战的用户

相关试题

完美数列(25)

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号