题目描述
给定一个正整数序列和一个正整数 p
。
如果 M≤m×p
成立,则该序列被称为完美序列,其中 M
和 m
分别是序列中的最大和最小数。
现在给定一个序列和一个参数 p
,你应该从序列中找到尽可能多的数字以构成一个完美的子序列。
输入格式
第一行包含两个整数 N
和 p
。
第二行包含 N
个正整数,表示给定序列。
输出格式
输出最多可以选择多少个数,构成一个完美子序列。
数据范围
1≤N≤105
,
1≤p≤109
,
序列中的元素均不超过 109
。
样例
输入样例:
10 8
2 3 20 4 5 1 6 7 8 9
输出样例:
8
算法1
(二分法) $O(nlogn)$
该题的关键是将数列排好序,从小开始遍历,找到符合条件的最后一个值,减去区间的起点m,即可得到本次完美数列的个数。
// 二分查找,找到符合该题条件的最大值 , 即这个区间的值符合该二分条件
import java.util.*;
import java.io.*;
class Main{
private static final int L = 100010;
private static int[] a = new int[L];
public static PrintWriter stdOut = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
public static BufferedReader stdIn = new BufferedReader(new InputStreamReader(System.in));
public static boolean check(int i, int j, int p){
if(a[i] > (long) a[j] * p){
return true;
}else{
return false;
}
}
public static int binarySearch(int l , int r, int p){
int min = l; // 这段区间里的最小值 // 这里找的是区间的最后一个值,因此最小值是不变的
while(l < r){
int mid = (l + r + 1) >> 1;
if(check(mid, min, p)){ // 区间内最小的肯定是l
r = mid - 1;
}else{
l = mid; // 我现在找到的是最后一个符合该条件的值的索引。
}
}
return r;
}
public static void main(String[] args) throws IOException{
String[] str = stdIn.readLine().split(" ");
int n = Integer.parseInt(str[0]);
int p = Integer.parseInt(str[1]);
str = stdIn.readLine().split(" ");
for(int i = 0; i < n; i++){
a[i] = Integer.parseInt(str[i]);
}
Arrays.sort(a, 0, n); // 排好序了
int m = 0, count = 0; // m 是最开始的值。
while(m <= n){
int l = m, r = n - 1;
count = Math.max(count, binarySearch(l, r , p) - m + 1); // 最后一个符合条件的减去一开始符合条件的第一个值
m++;
}
stdOut.println(count);
stdOut.flush();
}
}
时间复杂度
参考文献
算法2
(双指针移动) $O(n^2)$
类似于找区间的起点和终点,终点的指针不断加值,如果符合条件,继续加值,不符合条件,开始去除最小的,开始减值。最后计算区间长度。
时间复杂度
参考文献
java代码
import java.util.Arrays;
import java.util.Scanner;
import java.io.*;
public class Main {
private static final int L = 100010;
private static int[] a = new int [L];
public static BufferedReader stdIn = new BufferedReader(new InputStreamReader(System.in));
public static PrintWriter stdOut = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
public static void main(String[] args) throws IOException{
String[] str = stdIn.readLine().split(" ");
int N = Integer.parseInt(str[0]);
int p = Integer.parseInt(str[1]);
// int[] a = new int[N]; // 只开N个
String[] sp = stdIn.readLine().split(" ");
for(int i = 0; i < N; i++){
a[i] = Integer.parseInt(sp[i]);
}
Arrays.sort(a, 0, N); // 对原数组进行排序 方便找最大值和最小值
int j = 0, count = 0;
for(int i = 0; i < N; i++){
while(j < i && (a[i] > (long) a[j] * p)){ // 这里必须实时更新相应的最大值和最小值。
j++; // 数组 ++ 变成了下一个位置。
}
count = Math.max(count, i - j + 1);
}
stdOut.println(count);
stdOut.flush();
}
}