PAT Basic Level 1030 完美数列 （25 分）

题目链接:

https://pintia.cn/problem-sets/994805260223102976/problems/994805291311284224

本人6分代码:

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

int v[100010];
int m[10001][10001];

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

	int max_len = 0;
	sort(v, v + N);
	for(int i=0;i<N;i++)
		for (int j = i+1; j < N; j++)
		{
			m[i][j] = v[j] / v[i];
			int len = j - i+1;
			if (len>max_len&&(m[i][j] <= p)) {
				max_len = len;
			}
		}

	cout << max_len << endl;

AC代码:

/*
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>
#include <vector>
using namespace std;

int v[100010];
int m[10001][10001];

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

	int max_len = 0;
	sort(v, v + N);
	for(int i=0;i<N;i++)
		for (int j = i+1; j < N; j++)
		{
			m[i][j] = v[j] / v[i];//做除法不行，应该进行乘法，
			int len = j - i+1;
			if (len>max_len&&(m[i][j] <= p)) {
				max_len = len;
			}
		}

	cout << max_len << endl;
}
*/
#include<iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cctype>
using namespace std;

const int maxn=100010;
int n,p,a[maxn];

//二分查找可以用upper_bound代替
int binarySearch(int i,long long x){
    if(a[n-1]<=x)   return n;//如果所有数不大于x,返回n
    int l=i+1,r=n-1,mid;//在[i+1,n-1]查找
    while(l<r){
        mid=(l+r)/2;
        if(a[mid]<=x){
            l=mid+1;
        }
        else{
            r=mid;
        }
    }
    return l;//返回l或者r均可
}


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;//最大长度,初值为1
    for(int i=0;i<n;i++){
    //在a[i+1]~a[n-1]中查找第一个超过a[i]*p的数,返回其位置给j
        int j=binarySearch(i,(long long)a[i]*p);
    //  int j=upper_bound(a+i+1,a+n,(long long)a[i]*p)-a;
        ans=max(ans,j-i);
    }
    printf("%dn",ans);//输出结果
    return 0;
}

二刷:

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

#define Max 100000
long long arr[Max];

int main()
{
    long long N, P;
    cin>>N>>P;
    for(int i=0; i<N; i++ )
    {
        cin>>arr[i];
    }
    sort(arr,arr+N);
    long long i,j,ans=1;
    for(i=0;i<N;i++){
        for(j=i+ans;j<N;j++){
            if(arr[j]<=arr[i]*P){
                if(j-i+1>ans)
                    ans=j-i+1;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

最后

以上就是飞快毛衣为你收集整理的PAT Basic Level 1030 完美数列 （25 分）的全部内容，希望文章能够帮你解决PAT Basic Level 1030 完美数列 （25 分）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。