贪心

区间问题

思路：

输入样例：

3
-1 1
2 4
3 5

输出样例：

2

代码：

import java.util.*;


public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();

        int[][] range = new int[n][2];


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

        Arrays.sort(range, (x, y) -> x[1] - y[1]);

        int res = 0;
        int ed = (int)-2e9;

        for (int i = 0; i < n; i++) {
           if (range[i][0] > ed){
                res ++ ;
                ed = range[i][1];
            }
        }
        System.out.println(res);
    }
}

Huffman树

思路：

输入样例：

3 
1 2 9 

输出样例：

15

代码：

import java.util.*;

public class Main{
    static int N = 10010, n;
    static int[] a = new int[N];
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        Queue<Integer> minheap = new PriorityQueue<>();
        for(int i = 1; i <= n; i++){
            a[i] = in.nextInt();
            minheap.add(a[i]);
        }
        int res = 0;
        while(minheap.size() > 1){
            int x = minheap.poll();
            int y = minheap.poll();
            res += x + y;
            minheap.add(x + y);
        }
        System.out.println(res);
    }
}

绝对值不等式

思路：

中位数就是最优解

输入样例：

4
6 2 9 1

输出样例：

12

代码：

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n];
        for(int i = 0; i < n; i++){
            a[i] = in.nextInt();
        }
        Arrays.sort(a);
        long res = 0;
        for(int i = 0; i < n; i++){
            res += Math.abs(a[i] - a[n / 2]);
        }
        System.out.println(res);
    }
}