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;
}
网友评论