Given a sequence of positive integers and another positive integer p. The sequence is said to be a "perfect sequence" if M <= m * p where M and m are the maximum and minimum numbers in the sequence, respectively.
Now given a sequence and a parameter p, you are supposed to find from the sequence as many numbers as possible to form a perfect subsequence.
Input Specification:
Each input file contains one test case. For each case, the first line contains two positive integers N and p, where N (<= 105) is the number of integers in the sequence, and p (<= 109) is the parameter. In the second line there are N positive integers, each is no greater than 109.
Output Specification:
For each test case, print in one line the maximum number of integers that can be chosen to form a perfect subsequence.
Sample Input:
10 8
2 3 20 4 5 1 6 7 8 9
Sample Output:
8
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
long long num[];
bool cmp(long long a, long long b){
return a < b;
}
int binSearch(long long num[], int low, int high, long long m, long long p){
long long ans = p * m;
int mid = high;
while(low < high){
mid = (low + high) / ;
if(num[mid] > ans){
high = mid;
}else low = mid + ;
}
return low;
}
int main(){
int N, p, index, ans = -;
scanf("%d%d", &N, &p);
for(int i = ; i < N; i++)
scanf("%lld", &num[i]);
sort(num, num + N, cmp);
for(int i = ; i < N; i++){
index = binSearch(num, i + , N, num[i], p);
index--;
if(index - i + > ans){
ans = index - i + ;
}
}
printf("%d", ans);
cin >> N;
return ;
}
总结：
1、题意：给出一个数列和一个数字p，求满足M <= mp 的最长子数列， M与m分别为最大最小值。先对原数列排序一下，对比条件，显然M越大、m越小可以得到的子数列长度越长。因此可以从排好序的数列的两端往中间搜索答案，但是如果暴力二重循环会出现超时。因此，只能从左端递增遍历m， 而右端的M改用二分搜索，将复杂度变为 n*logn。
2、二分搜索M，目标是找到序列中尽可能靠右的且满足 M <= mp 的M， 即最后一个满足所给条件的M。这个可以转化为搜索第一个满足 M > mp 的num[i]。 则num[i - 1]即为最后一个满足M <= mp的M。
3、本题还可以使用两点法做，即使用两个指针，一遍扫描。如果a[j] <= a[i]* p成立，那么在[i, j]之内的任意k，都有a[k] <= a[i] *p成立，基于这一点设置i、j两个指针，j先递增，发现不等式不成立之后，i再向前走一步，如此反复。双指针法不仅可以一头一尾，也可以在同方向使用。代码如下：
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
long long num[];
bool cmp(long long a, long long b){
return a < b;
} int main(){
int N, p, index, ans = -;
scanf("%d%d", &N, &p);
for(int i = ; i < N; i++)
scanf("%lld", &num[i]);
sort(num, num + N, cmp);
int i = , j = ;
while(i < N && j < N){
long long temp = num[j] - num[i] * p;
if(temp <= ){
ans = max(ans, j - i);
j++;
}else{
i++;
}
}
printf("%d", ans + );
cin >> N;
return ;
}
4、二分搜索：
1）搜索满足某条件的元素。
int binSearch(int num[], int low, int high, int x){
int mid;
while(low <= high){ //当搜索区间为空时结束
mid = low + (high - low) / ;
if(num[mid] == x)
return mid;
else if(num[mid] > x)
high = mid - ;
else low = mid + ;
}
return -;
}
2）搜索第一个满足某条件的元素，在这个情况下要注意，被排好序的序列一定是从左到右先不满足条件，然后满足；另外，传入的high = N时，在搜索不到满足条件的数时，会返回N（假想N位置有数字）； 返回的是low而不是mid。
/*返回第一个大于等于x的元素。num[N]数组应从小到大排序。
如果传入的high = N，则当序列中所有元素都小于x时，会返回N */
int binSearch(int num[], int low, int high, int x){
int mid;
while(low < high){ //当low == high时结束搜索
mid = low + (high - low) / ;
if(num[mid] >= x)
high = mid; //mid有可能就是结果，所以区间上限不能漏掉mid
else low = mid + ;
}
return low; //返回low而不是mid
}