PAT 1030 完美数列 (25分)（Java）

题目描述

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

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

输入格式：

  输入第一行给出两个正整数 N 和 p，其中 N（≤10的5次方）是输入的正整数的个数，p（≤10的9次方）是给定的参数。第二行给出 N 个正整数，每个数不超过 10的9次方。

输出格式：

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

输入样例：

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

输出样例：

8

代码

package com.hbut.pat;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Pat_1030{
	public static void main(String args[]) throws IOException {
		InputStreamReader ir=new InputStreamReader(System.in);
		BufferedReader rd=new BufferedReader(ir);
		String []s=rd.readLine().split(" ");
		String []list=rd.readLine().split(" ");
		long []arr=new long[Integer.parseInt(s[0])];
		for(int i=0;i<list.length;i++) {
			arr[i]=Long.parseLong(list[i]);
		}
		quickSort(arr,0,list.length-1);
		int mi=0,ma=arr.length-1;
		long min=arr[mi],max=arr[ma],p=Integer.parseInt(s[1]);
		
		int num1=methd1(arr,mi,ma,p);
		int num2=methd2(arr,mi,ma,p);
		int num3=methd3(arr,mi,ma,p);
		if(num1>=num2&&num1>=num3&&num1>0) {
			System.out.println(num1);
		}
		else if(num2>=num1&&num2>=num3&&num2>0) {
			System.out.println(num2);
		}
		else if(num3>=num1&&num3>=num2&&num3>0) {
			System.out.println(num3);
		}
		else {
			System.out.println(0);
		}
	}
	public static int methd1(long arr[],int mi,int ma,long p) {
		boolean judge=true;
		long min=arr[mi],max=arr[ma];
		while(max>min*p) {
			if(judge) {
				ma-=1;
				max=arr[ma];
				judge=false;
			}
			else {
				mi+=1;
				min=arr[mi];
				judge=true;
			}
		}
		return ma-mi+1;
	}
	
	public static int methd2(long arr[],int mi,int ma,long p) {
		long min=arr[mi],max=arr[ma];
		while(max>min*p) {
				ma-=1;
				max=arr[ma];
		}
		return ma-mi+1;
	}
	public static int methd3(long arr[],int mi,int ma,long p) {
		long min=arr[mi],max=arr[ma];
		while(max>min*p) {
				mi+=1;
				min=arr[mi];
		}
		return ma-mi+1;
	}
	public static void quickSort(long[] arr,int low,int high){
        int i,j;long temp,t;
        if(low>high){
            return;
        }
        i=low;
        j=high;
        temp = arr[low];
 
        while (i<j) {
            while (temp<=arr[j]&&i<j) {
                j--;
            }

            while (temp>=arr[i]&&i<j) {
                i++;
            }

            if (i<j) {
                t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
            }
 
        }

         arr[low] = arr[i];
         arr[i] = temp;

        quickSort(arr, low, j-1);
        quickSort(arr, j+1, high);
    }
}

运行结果