[数据结构与算法]算法学习（二）

14天阅读挑战赛
努力是为了不平庸~
算法学习有些时候是枯燥的，这一次，让我们先人一步，趣学算法！欢迎记录下你的那些努力时刻（算法学习知识点/算法题解/遇到的算法bug/等等），在分享的同时加深对于算法的理解，同时吸收他人的奇思妙想，一起见证技术er的成长~

你可以从以下几个方面着手（不强制），或者根据自己对话题主题的理解创作，参考如下：

提醒：在发布作品前请把不用的内容删掉

算法知识点

贪心算法，何谓谓贪心，就是选择当前看来是最好，最优的一种策略。

算法题目来源

C语言网,地址：https://www.dotcpp.com/oj/problem2109.html

?

算法题目描述

输出格式有“最大”字眼。

做题思路

根据题意，从"最大战力算法平均值之和”出发，可分别算出n1,n2豪杰数所在城池的算法平均值。然后再相加。那怎样才能确保战力算法平均值最大呢，当然是将豪杰战力从大到小排序，然后从中抽取前n1+n2个数，那战力前n1+n2个豪杰怎么分配个两个城池呢？只有战力靠前的豪杰分配到所需豪杰最少的城池，然后将抽取出的剩下豪杰数分配给第二个城池，这种决策才是最优的，也符合贪心的

模板代码

import java.util.Arrays;
import java.util.Scanner;


// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

        public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
            double sum1=0;double average1=0;
            double sum2=0;double average2=0;
//        double n=in.nextDouble();
        int n=in.nextInt();

       int n1=in.nextInt();
       int n2=in.nextInt();

        int[] array=new int[ n];

         for(int i=0;i<n;i++)
         {
             array[i]=in.nextInt();
         }

        Arrays.sort(array);
//            for(int i=0;i<n;i++)
//            {
//                System.out.println(array[i]);
//            }
        int min=Math.min(n1,n2);
        if(min!=n1)
        { int t=n1;
            n1=n2;
            n2=t;

        }



            for(int i=array.length-1;i>array.length-1-min;i--)
            {

                sum1+=array[i];

            }
//            System.out.println(sum1);
             average1=sum1/min;
//            System.out.println(average1);

            for(int i=array.length-1-min;i>array.length-1-n1-n2;i--)
            {

                sum2+=array[i];

            }

//            System.out.println(sum2);

            average2=sum2/n2;
//            System.out.println(average2);
            System.out.printf("%.6f",average1+average2);
        }
//       public double average(int m){
//
//       }
//


    }

化简得

import java.util.Arrays;
import java.util.Scanner;
public class Main {

        public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        double sum1=0;double average1=0;
        double sum2=0;double average2=0;

        int n=in.nextInt();

        int n1=in.nextInt();
        int n2=in.nextInt();

        int[] array=new int[ n];

         for(int i=0;i<n;i++)
         {
             array[i]=in.nextInt();
         }

        Arrays.sort(array);//从小到大进行排序

        int min=Math.min(n1,n2);
        //保证城池n1为需要的最小豪杰数
        if(min!=n1)
        { int t=n1;
            n1=n2;
            n2=t;

        }


//n1组豪杰数的算术平均值
            for(int i=array.length-1;i>array.length-1-min;i--)
            {

                sum1+=array[i];

            }

             average1=sum1/min;

//n2组豪杰数的算法平均值
            for(int i=array.length-1-min;i>array.length-1-n1-n2;i--)
            {

                sum2+=array[i];

            }
            
            average2=sum2/n2;
//相加后格式输出
            System.out.printf("%.6f",average1+average2);
        }



    }

做题过程中遇到的bug及解决方案

格式输出不要弄错，做题前将思路理一遍，最好写在纸上。