PAT1085 Perfect Sequence(25)

//判断是否是连续的数
//判断是否只能第一个数是最小值
#include <cstdio>
#include <algorithm>
typedef long long ll;
using namespace std;
int n,p;
const int maxn = 100010;
int arr[maxn];int binary(int l, int r, ll tgt){if(arr[n-1] <= tgt) return n;while(l < r){int mid = (l+r) / 2;if(tgt < arr[mid]){r = mid;}else{l = mid+1;}}return l;
}
int main() {scanf("%d %d", &n, &p);for(int i = 0; i < n; i++){scanf("%d", &arr[i]);}sort(arr, arr+n);int res = 1;for(int i = 0; i < n; i++){int j = binary(i+1, n-1, (ll)arr[i]*p);res = max(res, j-i);}printf("%d\n", res);return 0;
}#双指针
//判断是否是连续的数
//判断是否只能第一个数是最小值
#include <cstdio>
#include <algorithm>
typedef long long ll;
using namespace std;
int n,p;
const int maxn = 100010;
int arr[maxn];int main() {scanf("%d %d", &n, &p);for(int i = 0; i < n; i++){scanf("%d", &arr[i]);}sort(arr, arr+n);int res = 1;int r = 0;for(int l = 0; l < n; l++){while(r < n && arr[r]<= (ll) arr[l]*p){r++;}res = max(res, r-l);}printf("%d\n", res);return 0;
}