B1030:完美数列(25')
思路:对数组a[N]从小到大排序,利用two pointers思想去解决。i从0开始,j从i+count开始。因为是找max的count,所以j初值设为i+count,不满足的话就直接j++。
注意:m*p可能会越界,所以改用long long型。
代码:
#include<stdio.h>
#include<algorithm>
using namespace std;
int main(){
long long N,p; //防止越界
scanf("%lld%lld",&N,&p);
long long a[N];
for(int i = 0;i < N;i ++){
scanf("%lld",&a[i]);
}
sort(a,a+N); //排序
int j = 0,count = 0;
for(int i = 0;i < N && j < N;i ++){
for(j = i + count;j < N && a[j] <= a[i]*p;j ++){ //j控制从i+count开始,因为是找max的count
count = max(count,j-i+1);
}
}
printf("%d",count);
return 0;
}
版权声明:本文为博主原创文章,未经博主允许不得转载。