排序子序列_组队竞赛

排序子序列

排序子序列


import java.util.Scanner;
public class Main{
  public static int subArray(int[] array){
      int count = 0;
      for(int i = 0;i<array.length-1;i++){

          //注意: 当 数组
          if(array[i]<array[i+1]){
              count++;
              while(i<array.length-1&&array[i]<=array[i+1]){
                  i++;
              }
          }else if(array[i]>array[i+1]){//这里需要用 else if!!!! 如果用else 就会将 ==划分给这里，而相等可以认为是升序子序列，也可认为是降序子序列！！！
               count++;
              while(i<array.length-1&&array[i]>=array[i+1]){
                  i++;
              }
          }
         if(i==array.length-2){//说明最后一个数为一个序列!
             count++;
         }
      }
      return count;
  }
  public static void main(String[] args){
      Scanner sc = new Scanner(System.in);
      while(sc.hasNext()){
          int n = sc.nextInt();
          int[] array = new int[n];
          for(int i = 0;i< n;i++){
              array[i] = sc.nextInt();
          }
          int result = subArray(array);
          System.out.println(result);
      }
  }
}

值得注意的是，这里当序列开始时是连续几个相等的数时，相等可以认为并不属于子序列！！！这里就自动跳过相等值就好！！！

组队竞赛

题目链接:组队竞赛

题目描述:
牛牛举办了一次编程比赛,参加比赛的有3*n个选手,每个选手都有一个水平值a_i.现在要将这些选手进行组队,一共组成n个队伍,即每个队伍3人.牛牛发现队伍的水平值等于该队伍队员中第二高水平值。
例如:
一个队伍三个队员的水平值分别是3,3,3.那么队伍的水平值是3
一个队伍三个队员的水平值分别是3,2,3.那么队伍的水平值是3
一个队伍三个队员的水平值分别是1,5,2.那么队伍的水平值是2
为了让比赛更有看点,牛牛想安排队伍使所有队伍的水平值总和最大。
如样例所示:
如果牛牛把6个队员划分到两个队伍
如果方案为:
team1:{1,2,5}, team2:{5,5,8}, 这时候水平值总和为7.
而如果方案为:
team1:{2,5,8}, team2:{1,5,5}, 这时候水平值总和为10.
没有比总和为10更大的方案,所以输出10.

解题

• 我们拿到题目先把题目问题读清楚!
• 然后我们进行分析题目!
• 根据题目描述,写解题思路!

我们可以先通过题目给的案例进行分析:
找到题解,然后再推广到全部情况,看是否满足!满足就说明思路正确,开始写代码!

• 示例分析:

显然:这就是数学的找规律问题!咱们多谢谢题就有感觉了!

import java.util.Scanner;
import java.util.Arrays;
public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()){
            int n = scanner.nextInt();
            int[] array = new int[n*3];
            for(int i = 0;i<n*3;i++){
                array[i] = scanner.nextInt();
            }
            //排序
            Arrays.sort(array);
            long result = 0;
            for(int i = 0;i<n;i++){
            //找中间值
                result += array[array.length-2*(i+1)];
            }
           System.out.println(result);
        }

    }
}