完美数列(25)

[编程题]完美数列(25)

热度指数：30583 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个正整数数列，和正整数p，设这个数列中的最大值是M，最小值是m，如果M <= m * p，则称这个数列是完美数列。

现在给定参数p和一些正整数，请你从中选择尽可能多的数构成一个完美数列。

输入描述:

输入第一行给出两个正整数N和p，其中N（<= 10⁵）是输入的正整数的个数，p（<= 10⁹）是给定的参数。第二行给出N个正整数，每个数
不超过10⁹。

输出描述:

在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。

示例1

输入

10 8
2 3 20 4 5 1 6 7 8 9

输出

算法知识视频讲解

Java

WZL0x7f

先排序，然后在按小的数枚举，找出从小的数开始到数组结尾

import java.util.*;

public class Main{
	    public static void main(String[] args){
	    	Scanner sc = new Scanner(System.in);
	    	int n = sc.nextInt();
	    	long p = sc.nextLong();
	    	long [] arr = new long [n];
	    	for (int i = 0; i < arr.length; i++) {
				arr[i] = sc.nextLong();
			}
	    	Arrays.sort(arr);
	    	int max = 0, index = 0;
	    	long maxNum = 0;
	    	for(int i = 0; max <= n - i || i < n; i++){ //i不能越界，其次要是数组里剩余的数还比找的max还少，那就不用枚举了
	    		maxNum = arr[i] * p;
	    		index = getIndex(arr, i, maxNum);
	    		if(index != -1){
	    			max = Math.max(max, index - i + 1);
	    		}
	    	}
	    	System.out.println(max);
	    }

		private static int getIndex(long[] arr, int i, long maxNum) {
			int l = i, h = arr.length - 1, mid = 0;
			while(l <= h){
				mid = l + (h - l) / 2;
				if(arr[mid] == maxNum) return mid;
				else if(arr[mid] < maxNum){
					l = mid + 1;
				}else {
					h = mid - 1;
				}
			}
			if(arr[mid] < maxNum) return mid;
			return mid - 1;
			
		}
	    
}

里面m*p所覆盖的最长距离即可。

发表于 2019-08-19 17:41:12 回复(2)

Java

任彦州

import java.util.Arrays;
import java.util.Scanner;
public class Main{
 public static void main(String[] args) {
  Scanner in=new Scanner(System.in);
  int n=in.nextInt();
  int p=in.nextInt();
  int []num=new int[n];
  for(int i=0;i<n;i++) {
   num[i]=in.nextInt();
  }
  Arrays.sort(num);
        int result=0;
        for(int i=0;i<num.length;i++) {
         for(int j=i+result;j<num.length;j++) {
          if(num[j]<=num[i]*p) {
           if(j-i+1>result) {
            result=j-i+1;
           }
          }
          else {
           break;
          }
         }
        }
  System.out.println(result);
 }
}

发表于 2019-03-23 11:16:11 回复(0)

Java

5天

  
    先对数组排序；从小大到使用二分法寻找数组元素对应最大元素值，并且每一次搜索的上界都是由上一个元素对应最元素值对应位置决定；当搜索最大元素位置超过给出数组的长度，则结束搜索
  
  importjava.util.*; 

  publicclassMain{ 

      publicstaticvoidmain(String[] args) { 

          Scanner in = newScanner(System.in); 

          intN = in.nextInt(); 

          intP = in.nextInt(); 

          int[] sequ = newint[N]; 

          for(intk = 0; k < N; k++) { 

              sequ[k] = in.nextInt(); 

          } 

          Arrays.sort(sequ); 

          intmax = 0; 

          intlo = 0; 

          for(inti = 0; i < sequ.length; i++) { 

              intindex = searchIndex(sequ[i]*P, sequ, lo,
  sequ.length-1); 

              if(index == sequ.length){ 

                  break; 

              } 

              max = index - i+1> max ? index - i+1: max; 

              lo = index; 

          } 

          System.out.print(max); 

      } 

      privatestaticintsearchIndex(intx, int[] sequ, intlo, inthi) { 

          if(lo > hi){ 

              returnhi; 

          } 

          intmid = (lo+hi)/2; 

          if(sequ[mid] > x) { 

              returnsearchIndex(x, sequ, lo, mid-1); 

          }elseif(sequ[mid] < x) { 

              returnsearchIndex(x, sequ, mid + 1, hi); 

          }else{ 

              returnmid; 

          } 

      } 

  }