PAT 甲级 1085 Perfect Sequence (25 分) +二分相关知识

超、凢脫俗 2024-02-19 21:55 63阅读 0赞

## 1085 Perfect Sequence (25 分) ##

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.

#### Input Specification: ####

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.

#### Output Specification: ####

For each test case, print in one line the maximum number of integers that can be chosen to form a perfect subsequence.

#### Sample Input: ####

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

#### Sample Output: ####

二分的相关知识：

头文件： \#include<algorithm>

对于一个数组 a\[\] 要求a\[\] 数组有序

upper\_bound(a+i,a+j,x)-a //返回第一个大于x的数的位置

low\_bound(a+i,a+j,x)-a //返回的是第一个大于等于x的数的位置

例

a\[\]=\{1,2,3,4,4,4,4,5\}

upper\_bound(a,a+8,4) //返回7

low\_bound(a,a+8,4) //返回3

这两个算法其实是采用的二分查找

upper\_blound

void uppper_blound(int l,int r,int x){
          while(l<r）{
            int mid=(r-l)/2;
            if(a[mid]>x) r=mid;
            else  l=mid+1;
        }
    }

low\_bound

void low_bound(int l,int r,int x){
       while(l<r){
           int mid=(r-l)/2;
           if(a[mid]>=x) r=mid;
           else l=mid+1;
        }
    }

附上一个STL里的二分

[https://blog.csdn.net/nisxiya/article/details/44945441][https_blog.csdn.net_nisxiya_article_details_44945441]

我的代码：

#include<iostream>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    int cmp(long long a,long long b)
    {
    	return a<b;
    }
    
    long long a[100005];
    int main()
    {
    	int n,p,i,j,cnt=0;
    	long long temp=0;
    	cin>>n>>p;
    	for(i=0;i<n;i++)
    	cin>>a[i];
    	sort(a,a+n,cmp);
    	for(i=0;i<n;i++)
    	{
    		temp=a[i]*p;
    		j=upper_bound(a+i+1,a+n,temp)-(a+i);
    		cnt=max(j,cnt);
    	}
    	cout<<cnt<<endl;
    	return 0;
    }

[https_blog.csdn.net_nisxiya_article_details_44945441]: https://blog.csdn.net/nisxiya/article/details/44945441