题目
PAT 甲级 1085 Perfect Sequence (25分) 二分
思路
易错点
1 特殊情况：序列中所有数都不超过a[i]*p，要返回n
题解
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std
;
const int maxn
= 100010;
int n
,p
;
long long a
[maxn
];
int upper_bunder(long long arr
[],int l
,int r
,long long x
){
if(arr
[r
]<=x
)return r
+1;
int mid
;
while(l
<r
){
mid
= l
+((r
-l
)>>1);
if(arr
[mid
]>x
){
r
= mid
;
}else{
l
= mid
+1;
}
}
return l
;
}
int main(int argc
,char * argv
[]){
scanf("%d%d",&n
,&p
);
for(int i
=0;i
<n
;i
++){
scanf("%lld",&a
[i
]);
}
sort(a
,a
+n
);
int ans
= 1;
for(int i
=0;i
<n
;i
++){
long long tmp
= a
[i
]*p
;
int j
= upper_bunder(a
,i
+1,n
-1,tmp
);
ans
= max(ans
,j
-i
);
}
printf("%d\n",ans
);
return 0;
}
