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

冷不防 2021-09-24 02:50 260阅读 0赞

## 题目描述 ##

给定一个正整数数列，和正整数 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

## 输出样例： ##

## 代码 ##

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);
        }
    }

## 运行结果 ##

![在这里插入图片描述][20200402131356597.png]

[20200402131356597.png]: /images/20210923/d2d692a73d594de6818907e742c64985.png