美文网首页
B1030 完美数列 (25分)

B1030 完美数列 (25分)

作者: km15 | 来源:发表于2020-02-03 12:55 被阅读0次

include <iostream>

include <algorithm>

using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop /
/

题意:
1、找最大值,和最小值,给以p,最大值<= np,则是完美数列
2、给定N个数,问,可以选择多少个数组成一个完美数列?

解题:
1、

learn && worng:
1、解题思路
2、


*/ 

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

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

int binarysearch(int i,long long x){
    if(a[n - 1] <= x) return n; //如果所有数都不大于x,返回
    int l = i + 1, r = n - 1,mid; //在[i + 1, n - 1]内查找
    while(l < r){
        mid = (l + r) / 2;
        if(a[mid] <= x){ //若a[mid] <= x,说明第一个大于x的数只能在mid后面 
            l = mid + 1;  //左端点即为mid + 1 
        }else{  //若a[mid] > x,说明你第一个大于x的数在mid之前(含mid)
         r = mid; //若a[mid] > x,说明第一个大于x的数在mid之前(含mid) 
        }
         
    } 
    return l; //由于while结束时候 l == r,因此返回l或者rdoukeyi  
} 

int main(int argc, char** argv) {
    
    scanf("%d%d", &n,&p);
    for(int i = 0;i < n;++i){
        scanf("%d" ,&a[i]);
    }
    
    sort(a,a+n); //递增排序 
    int ans = 1;//最大長度,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);
        ans = max(ans, j - i); //更新最大长度 
    } 
    cout<<ans<<endl;
    return 0;
}

有的过不了
long long array1[100010]; 

bool cmp(long long a,long long b){
    return a < b;
}

int main(int argc, char** argv) {
    int n,p;
    cin>>n>>p;
    for(int i = 0;i < n;++i){
        cin>>array1[i];
    }
    
    sort(array1,array1 + n,cmp);
    
    int ans = 0;
    //如何实现呢
    for(int i = 0;i < n;++i){
        if(array1[i] <= array1[0] * p)
        ans++;
    } 
            
    cout<<ans<<endl;
    return 0;
}

相关文章

  • B1030 完美数列 (25分)

    include include using namespace st...

  • B1030 完美数列 (25分)

    题意:1、给定N个数,和一个权重P,要求,最大值M<=mp(最小值乘以p),求着N个数中最多可以构成完美数列的数字...

  • 1030 完美数列

    给定一个正整数数列,和正整数 p,设这个数列中的最大值是 M,最小值是 m,如果 M≤mp,则称这个数列是完美数列...

  • PAT-B 1030 完美数列(C语言)

    题目 链接:PAT (Basic Level) Practice 1030 完美数列 给定一个正整数数列,和正整数...

  • 1030.完美数列

    题目描述 给定一个正整数数列,和正整数p,设这个数列中的最大值是M,最小值是m,如果M <= m * p,则称这个...

  • 1030 完美数列 (25 分)

    此题只有23分,测试点5暂未通过

  • 2018-10-22 完美数列

    题目描述 给定一个正整数数列,和正整数p,设这个数列中的最大值是M,最小值是m,如果M <= m * p,则称这个...

  • PAT 1030 完美数列 (25 分)

    GitHub

  • 数学分析理论基础7:数列极限存在的条件

    数列极限存在的条件 单调数列 定义:若数列的各项满足关系式,则称数列为递增(递减)数列,递增数列和递减数列统称为单...

  • Python练习

    练习清单 寻找“水仙花数”。 寻找“完美数”。 “百钱百鸡”问题。 生成“斐波拉切数列”。 Craps赌博游戏。 ...

网友评论

      本文标题:B1030 完美数列 (25分)

      本文链接:https://www.haomeiwen.com/subject/gkwqxhtx.html