美文网首页
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分)

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