首页 > 试题广场 >

Perfect Sequence (25)

[编程题]Perfect Sequence (25)
  • 热度指数：2933 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
Given a sequence of positive integers and another positive integer p. The sequence is said to be a "perfect sequence"

if M <= m * p where M and m are the maximum and minimum numbers in the sequence, respectively.



Now given a sequence and a parameter p, you are supposed to find from the sequence as many numbers as possible

to form a perfect subsequence.

输入描述:
Each input file contains one test case. For each case, the first line contains two positive integers N and p, where N (<= 
105) is the number of integers in the sequence, and p (<= 109) is the parameter. In the second line there are N 
positive integers, each is no greater than 109.


输出描述:
For each test case, print in one line the maximum number of integers that can be chosen to form a perfect subsequence.
示例1

输入

10 8<br/>2 3 20 4 5 1 6 7 8 9

输出

8
算法知识视频讲解
添加回答
C/C++
Xtion头像 Xtion
这不水题吗，为啥通过率这么低，害我写得时候小心翼翼的。。。 
#include<iostream>
#include<algorithm>
using namespace std;

#define MAX     100009

int N, p;
int nset[MAX];
int max_len = 0;

int main(void)
{
    cin >> N >> p;
    for (int i = 0; i < N; ++i) {
        cin >> nset[i];
    }

    (void)sort(nset, nset + N);
    
    int imin = 0;
    int imax = 0;
    while (1) {
        if (nset[imax] > nset[imin] * p) {
            ++imin;
            continue;
        }
        
        max_len = max(max_len, imax - imin + 1);

        if (++imax == N) {
            break;
        }

    }

    cout << max_len;

    return 0;
}


发表于 2021-05-04 17:39:07 回复(0)
江左哥哥头像 江左哥哥 
//
// Created by 江左 on 2021/1/31.
//

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

int main()
{
    int N, p;
    cin >> N >> p;
    long *a=new  long[N];
    for (int i = 0; i < N; i++)
        cin >> a[i];
    sort(a, a + N);
    int res = 0;//数列的最大长度
    for (int i = 0; i < N; i++) {//找以各个元素为最小值的，完美数列的最大长度
        for (int j = i + res; j < N; j++) {//直接从i+res的索引开始，因为前面的没必要比了。妙不可言
            if (a[j] <= a[i] * p)
                res++;
            else break;
        }
    }
    cout << res;

}

发表于 2021-01-31 19:27:41 回复(0)
Python
初心者托奇头像 初心者托奇 
a = list(map(int,input().split()))
b = sorted(list(map(int,input().split())))
i,k = 0,1
while i + k < a[0]:
    if b[i] * a[1] >= b[i + k]:
        k += 1
    else:
        i += 1
print(k)

编辑于 2020-02-05 17:36:42 回复(0)
C/C++
北川不下雪头像 北川不下雪
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=100005;
int a[maxn];
int main(int argc, const char * argv[]) {
    int n,p;
    cin>>n>>p;
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);
    int maxlen=0;
    for(int i=0;i<n;i++){
        if(i+maxlen>=n) break;
        for(int j=i+maxlen;j<n;j++,maxlen++)
            if(a[j]>a[i]*p) break;
    }
    cout<<maxlen;
    return 0;
}
发表于 2019-12-05 20:39:25 回复(0)
棠荼头像 棠荼 
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	long p,a[100001]={0};
	int i,n,m,max,k,l;
	cin>>n>>p;
	for(i=0;i<=n-1;i++)
	cin>>a[i];
	sort(a,a+n);
	i=0;
	max=0;
	while(i+max<n)
	{
		if(a[i+max]>a[i]*p)
			i++;
		else 
			max++;
	}
	cout<<max;
	return 0;
}
/*
10 8
2 3 20 4 5 1 6 7 8 9
*/

发表于 2019-10-10 09:37:42 回复(0)
予妤。头像 予妤。 
#include<bits/stdc++.h>
using namespace std;

int main(){
    int n,p,i,l,m,r,maxn=0;
    int a[100010];
    cin>>n>>p;
    for(i=0;i<n;i++) cin>>a[i];
    sort(a,a+n);
    for(i=0;i<n;i++){
        l=i;
        r=n-1;
        while(l<=r){
            m=(l+r)/2;
            if(a[m]<=a[i]*p){
                maxn=max(maxn,m-i+1);
                l=m+1;
            }else r=m-1;
        }
    }
    cout<<maxn; 
    return 0;
} 

编辑于 2019-02-13 11:20:12 回复(0)
RicardoZi头像 RicardoZi 
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100000 + 10;
int num[maxn];
int main(){
    int n, p;
    int ans = 1;
    scanf("%d %d", &n, &p); 
    for(int i=0; i<n; i++)
        scanf("%d", &num[i]);
    sort(num, num+n);
    for(int i=0; i<n; i++){
        int j = upper_bound(num+i+1, num+n, (long long)num[i]*p) - num;
        ans = max(ans, j-i);
    }
    printf("%d\n", ans);
    return 0;
}

编辑于 2017-09-03 22:38:49 回复(0)
啥头像 啥 
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    // 读入数据
    int N, p; cin >> N >> p;
    vector<int> data(N);
    for(int i=0; i<N; i++) {
        cin >> data[i];
    }

    // 处理数据
    sort(data.begin(), data.end());
    int maxNum = 0;
    for(int i=0; i<N; i++) {
        while(i+maxNum<N && data[i+maxNum]<=data[i]*p) {
            maxNum++;
        }
    }
    cout << maxNum << endl;
    return 0;
}


发表于 2015-12-27 11:29:49 回复(2)
2207头像 2207
//前缀数组用的话要是最大值比较小时间复杂度O(n)
#include <iostream>
#include <algorithm>
using namespace std;

const int mmaxint=0xffff;
const int maxn=100010;
int n,p;

int num[maxn];

int c[mmaxint];

int maxnum;

int maxresult;

int main(){

    cin>>n>>p;

    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        num[i]=x;
        c[x]+=1;
        maxnum=max(maxnum,x);
    }
    for(int i=1;i<=maxnum;i++){
        c[i]+=c[i-1];
    }

    for(int i=0;i<n;i++){
        int up=min(maxnum,p*num[i]);
        maxresult=max(maxresult,c[up]-c[num[i]-1]);
    }

    cout<<maxresult<<endl;

    return 0;
}
发表于 2020-07-23 02:20:21 回复(0)
默默丶头像 默默丶
排序过后，从小依次向大的方向找，当前遍历的一定是最大值M，然后记录最小值m及其下标，当满足时，继续循环，当不满足时最小值下标++并更改最小值，继续本次循环（i不变） 
#include<iostream>
(720)#include<vector>
#include<algorithm>
using namespace std;
int main(){
    int n,p,x;
    cin>>n>>p;
    vector<int>sequence;
    for(int i=0;i<n;i++){
        cin>>x;
        sequence.push_back(x);
    }
    sort(sequence.begin(),sequence.end());
    int count=0,smin=sequence[0],minIndex=0;
    for(int i=0;i<n;i++){
        int smax=sequence[i];//最大的始终是当前的
        if(smax<=smin*p){
            count=max(count,i-minIndex+1);
        }
        else{
            minIndex++;2
            smin=sequence[minIndex];3
            i--;//i不变
        }
    }
    printf("%d",count);
}
         


发表于 2020-04-01 11:02:24 回复(0)
BlackCarDriver头像 BlackCarDriver
填楼 
#include<stdio.h>
(737)#include<iostream>
#include<vector>
(721)#include<string>
#include<algorithm>
(831)#include<set>
using namespace std;

int number, parameter;
int main(){
	scanf("%d %d", &number, &parameter);
	vector<int> data(number);
	for (int i = 0; i < number; i++){
		scanf("%d", &data[i]);
	}
	sort(data.begin(), data.end());
	vector<int>::iterator head=data.begin(), tail=data.begin();
	int ans = 0;
	while (head < data.end() && tail < data.end() && head <= tail){
		while (tail < data.end() && *tail <= (*head * parameter)) tail++;
		ans = (ans>tail-head? ans: tail-head);
		head++;
	}
	cout << ans << endl;
	return 0;
}


发表于 2020-03-02 10:50:53 回复(0)
成为offer收割机1头像 成为offer收割机1

/ 求最长的满足关系Max<minp的序列长度
首先进行输入的排序
然后在查找最长，这里注意一点就是查找到的最小和最大的数之间的数构成的序列不是真正的最长，所以得再加一个判断条件*/

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

public static void main(String[] args) throws Exception {
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    String []str=reader.readLine().split(" ");
    StringTokenizer stringTokenizer=new StringTokenizer(reader.readLine());
    int N=Integer.parseInt(str[0]);
    long  p=Integer.parseInt(str[1]);
    int []num=new int[N];
    for(int i=0;i<N;i++)
    {
        num[i]=Integer.parseInt(stringTokenizer.nextToken());
    }
    Arrays.sort(num);
    int maxNum=0;
    for(int i=0; i<N; i++) {
        for(int j=i+maxNum;j<N;j++)
        {
            if(num[i]*p>=num[j]) {maxNum++;}
            else
                break;
        }
    }
    System.out.println(maxNum);

}

}

发表于 2018-11-01 20:05:43 回复(0)
袁博文202头像 袁博文202 
from bisect import bisect_right

n, p = map(int, input().split())
a = sorted(list(map(int, input().split())))
ans = 0
for i in range(n):
    j = bisect_right(a, a[i]*p, i, n)
    ans = max(ans, j-i)
    if j==n: break

print(ans)

发表于 2018-05-02 16:26:38 回复(0)
C/C++
OFShare头像 OFShare 
//排序后二分即可
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int n,p,A[maxn];
int main(){
    scanf("%d %d",&n,&p);
    for(int i=1;i<=n;++i)
        scanf("%d",&A[i]);
    sort(A+1,A+1+n);
    int ans=0;
    for(int i=1;i<=n;++i){
        long long tmp=A[i]*p;
        ans=max(ans,int(upper_bound(A+1,A+1+n,tmp)-(A+i)));
    }
    printf("%d\n",ans);
    return 0;
}

发表于 2018-03-17 20:22:03 回复(0)
大傻1111头像 大傻1111 

	//这道题要注意的点：





	//1.数据类型要设置为long，否则在PAT官网的OJ上最后一个测试点过不去- -





	//2.优化查找算法，看代码





	#include<iostream>





	#include<algorithm>





	#include<vector>





	using namespace std;





	int main(){    





	    int n,p;





	    cin>>n>>p;





	    vector<int> arr(n);





	    for(int i=0;i<n;i++) cin>>arr[i];





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





	    int max = 0;





	    for(int i=0;i<n;i++){





	        while(i+max<n&&arr[i+max]<=arr[i]*p){





	            max++;





	        }





	    }





	    cout<<max<<endl;





	    return 0;





	}

发表于 2018-03-14 10:20:31 回复(0)
雨滋润的地方头像 雨滋润的地方
题意：满足条件：Max < min * p，即为完美数列，只要注意这个min，与p皆在10^9以内，在int范围内，           但是min * p就可能超过int 10^10范围了，所以要用long long 类型
思路：1.二分
          2.two pionter
          皆可做
#include <cmath>
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main() 
{     
freopen("C:\\Documents and Settings\\Administrator\\桌面\\data.txt", "r", stdin);
int n, p;
vector<int> num;  //记录整个序列
scanf("%d%d", &n, &p);
num.resize(n);    //将数组序列大小更新为n
int temp;       
for (int i = 0; i < n; i++)
{
scanf("%d", &temp);
num[i] = temp;
}
sort(num.begin(), num.end());     //将其升序排列
int front = 0, back = 0, ans = 1; //two pointer front与back指针分别指向完美子序列的前后两端
/*
下面这段有两种写法
while (front < n && back < n)
{
   while (front < n && num[front] <= (long long) num[front] * p)
{
   ans = max(ans, front - back + 1);
front++;
}
back++;
}
*/
    while (front < n && back < n)     //遍历一遍序列即可
{
if (num[front] <= (long long )num[back] * p) //num[back]与p均大于10^9，因而num[back]*p可达10^18，需转换成long long类型
{
ans = max(ans, front - back + 1); //更新ans，即当前完美子序列的最大元素个数
front++;           //满足完美序列条件，前端指针自增
}
else              
{
back++;            //不满足时，后端指针自增
}
}
printf("%ld\n", ans);
while (1);
return 0;
}


发表于 2017-09-04 20:19:05 回复(0)
牛客559967号头像 牛客559967号
时间复杂度O(NlogN) 
#include "stdafx.h"
#include<cstdio>
#include<vector>
#include <algorithm>
using namespace std;
int main()
{
	long long numberAmount, P;
	scanf("%lld %lld", &numberAmount, &P);
	vector<long long> nums(numberAmount);
	for (long long i = 0; i < numberAmount;i++)
	{
		scanf("%lld", &nums[i]);
	}
        //按从小到大排序
	sort(nums.begin(), nums.end());
        //设置l和r分别表示perfect sequence两端，最长序列初始长度为1
	size_t l = 0, r = 0;
	long long maxLen = 0;
	for (; r < nums.size();)
	{
		auto prod = nums[l] * P;
                //满足perfent sequence要求
		if(nums[r]<=prod)
		{
                        //如果当前perfect sequence是最长的，记录长度
			if(r-l+1>maxLen)
			{
				maxLen = r - l + 1;
			}
                        //我们希望perfect sequence尽可能长，所以右移r r++;
		}else
		{
                        //不满足perfect sequence,增大序列最小值
			l++;
		}
	}
	printf("%lld", maxLen);
	return 0;
}

编辑于 2017-02-26 21:46:20 回复(2)
ieesky头像 ieesky
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner cin  = new Scanner(System.in);
        while(cin.hasNext()){
            int n = cin.nextInt();
            int p = cin.nextInt();
            int[] a = new int[n];
            for(int i=0;i<n;i++)
                a[i] = cin.nextInt();
            Arrays.sort(a);
            int jump = 0;
            int max = 0;
            for(int i=0;i<n;i++){
                int k = i+jump;
                if(k>=n)
                    break;
                int M = a[i]*p;
                int l = jump;
                while(k<n){
                    if(a[k]<=M){
                        l++;
                        k++;
                        max=l>max?l:max;
                    }else{
                        jump=l-1;
                        break;
                    }
                }
            }
            System.out.println(max);
        }
        cin.close();
    }

}
发表于 2015-06-11 20:51:11 回复(0)
提交观点

问题信息

字符串
来自：程序员编程能力鉴定(甲级)
难度：
18条回答 7394浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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