贪心--HOJ-1062-数列极差问题

本是古典何须时尚 2022-05-24 03:27 109阅读 0赞

## 数列极差问题 ##

题意：N个正整数组成的一个人数列，并进行如下操作：每次擦去其中的两个数a和b，然后在数列中加人一个数a\*b+1，如此下去直至剩下一个数，按这样的方式最后得到的数中 最大为max，最小为min，极差的定义为max-min；请你编程求极差；

输入格式：输入有多组数据，第一个数N表示长度（0--50000），随后是N个正整数。

1 2 3

8 6 5 9 7 1

输出：

3672

## 分析：max是每次合并的最小的两个数相乘，min是每次合并的最大的两个数相乘 ##

代码如下：

package 贪心;
    
    import java.util.Arrays;
    import java.util.Scanner;
    
    public class 数列极差问题 {
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		Scanner in = new Scanner(System.in);
    		while(in.hasNext()){
    			int n = in.nextInt();
    			int m[] = new int[n];
    			for(int i = 0;i<n;i++){
    				m[i] = in.nextInt();
    			}
    			int[] kk = m;
    			int[] kkk = m;
    			for(int i = 0;i<n-1;i++){
    				kk = min(kk);
    				kkk = max(kkk);
    			}
    			System.out.println(kkk[0]-kk[0]);
    			
    		}
    	}
    	public static int[] min(int[] m) {
    		int mm[] = new int[m.length];
    		int k = 0;
    		Arrays.sort(m);
    		for(int i = m.length-1;i>=0;i--){
    			mm[k++] = m[i];
    		}
    		int kk[] = new int[m.length-1];
    		kk[0] = mm[0]*mm[1]+1;
    		int k1 = 1;
    		for(int i = 2;i<m.length;i++){
    			kk[k1++] = mm[i];
    		}
    		return kk;
    	}
    	public static int[] max(int[] m) {
    		int mm[] = new int[m.length];
    		int k = 0;
    		Arrays.sort(m);
    		for(int i = 0;i<m.length;i++){
    			mm[k++] = m[i];
    		}
    		int kk[] = new int[m.length-1];
    		kk[0] = mm[0]*mm[1]+1;
    		int k1 = 1;
    		for(int i = 2;i<m.length;i++){
    			kk[k1++] = mm[i];
    		}
    		return kk;
    	}
    }