B1030 完美数列 (25分)

2020-02-03  本文已影响0人  km15

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;
}
上一篇下一篇

猜你喜欢

热点阅读