第3章 排序的使用

1、分数线

算法分析

二分

• check(x):表示用x表示获奖分数，获奖人数是否大于等于参赛总人数，取左边区域的最大值

时间复杂度

Java 代码

import java.util.Scanner;

public class Main{
    static int N = 100010;
    static int n;
    static int[] a = new int[N];
    static boolean check(int x)
    {
        int res = 0;
        for(int i = 0;i < n;i ++)
            if(a[i] >= x) res ++;
        
        return res >= (n + 1 >> 1);
    }
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        for(int i = 0;i < n;i ++) a[i] = scan.nextInt();
        int l = 0,r = 100;
        while(l < r)
        {
            int mid = l + r + 1 >> 1;
            if(check(mid)) l = mid ;
            else r = mid - 1;
        }
        int cnt = 0;
        for(int i = 0;i < n;i ++) 
            if(a[i] >= l)
                cnt ++;
        System.out.println(l + " " + cnt);
        
    }
}

2、红蓝绿

算法分析

• 1、先对数组进行排序，输出
• 2、res表示最多能组成的幸福串，res = min(numB / 3, numG / 2,numR)，

时间复杂度

Java 代码

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

public class Main{
    
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        char[] temp = scan.next().toCharArray();
        int len = temp.length;
        Arrays.sort(temp,0,len);
        System.out.println(String.valueOf(temp));
        
        int numB = 0;
        int numG = 0;
        int numR = 0;
        for(int i = 0;i < len;i ++) 
        {
            if(temp[i] == 'B') numB ++;
            if(temp[i] == 'G') numG ++;
            if(temp[i] == 'R') numR ++;
        }
        int res = Math.min(numB / 3, numG / 2);
        res = Math.min(res, numR);
        System.out.println(res);
    }
}

3、交叉排序

算法分析

暴力操作

时间复杂度

Java代码

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

public class Main{
    static int N = 100010;
    static int[] a = new int[N];
    static int[] tmp = new int[N];
    public static void main(String[] args) {
       Scanner scan = new Scanner(System.in);
       int n = scan.nextInt();
       int l1 = scan.nextInt();
       int r1 = scan.nextInt();
       int l2 = scan.nextInt();
       int r2 = scan.nextInt();
       for(int i = 1;i <= n;i ++) a[i] = scan.nextInt();
       
       Arrays.sort(a,l1,r1 + 1);
       
       for(int i = l2;i <= r2;i ++) tmp[i] = a[i];
       Arrays.sort(tmp,l2,r2 + 1);
       
       for(int i = r2,j = l2;i >= l2;i --,j ++)
            a[j] = tmp[i];
       
       for(int i = 1;i <= n;i ++) 
       {
           if(i != n) System.out.print(a[i] + " ");
           else System.out.println(a[i]);
       }
     }
}

4、前k名的平均数

算法分析

先排序，在找前k名的平均数

时间复杂度

Java 代码

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

public class Main{
    static int N = 35;
    static int[] a = new int[N];
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        for(int i = 0;i < n;i ++) a[i] = scan.nextInt();
        int k = scan.nextInt();
        Arrays.sort(a,0,n);
        double sum = 0;
        for(int i = n - 1,j = 0;j != k;i --,j ++)
        {
            sum += a[i];
        }
        System.out.printf("%.2f",sum / k);
    }
}