第9章 贪心算法

2、节约用电

算法分析

排序+双指针
start表示上一个亮着的灯，j从start + 1开始枚举，若a[j + 1] - a[start] <= m，则表示当前位置j的灯需要灭掉

时间复杂度

Java 代码

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

public class Main{
    static int N = 100010; 
    static int[] a = new int[N];
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        for(int i = 1;i <= n;i ++) a[i] = scan.nextInt();
        Arrays.sort(a,1,n + 1);
        
        int res = 0;
        for(int start = 1;start < n;start ++)
        {
            int j = start + 1;
            while(j < n && a[j + 1] - a[start] <= m)
            {
                res ++;
                j ++;
            }
            start = j - 1;
        }
        
        System.out.println(res);
    }
}

3、蘑菇森林

算法分析

这题问的其实是最多能死多少值蘑菇怪
血量值从小到大排序，若能击败就击败

时间复杂度

Java 代码

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

public class Main{
    static int N = 5010; 
    static Pair[] pair = new Pair[N];
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        int aim = scan.nextInt() + scan.nextInt();
        for(int i = 0;i < n;i ++)
        {
            int x = scan.nextInt();
            int y = scan.nextInt();
            pair[i] = new Pair(x,y);
        }
        Arrays.sort(pair,0,n);
        int res = 0;
        for(int i = 0;i < n;i ++)
        {
            int x = pair[i].x;
            int y = pair[i].y;
            if(aim >= x && m >= y)
            {
                m -= y;
                res ++;
                if(m <= 0) break;
            }
        }
        System.out.println(res);
    }
}
class Pair implements Comparable<Pair>
{
    int x,y;//x - 闪现，y - 血量
    Pair(int x,int y)
    {
        this.x = x;
        this.y = y;
    }
    @Override
    public int compareTo(Pair o) {
        // TODO 自动生成的方法存根
        return Integer.compare(y, o.y);
    }
    
}