顺丰科技2021研发岗笔试：贪心算法应用

/**
 *   小 A 购买了一批服务器，他准备将这批服务器租用出去，每一个服务器都有一个固定的带宽，人们根据自己的需要来租用这些服务器，
 *   一台服务器只能租给一个人，
 *   小A 现在有 n 个空闲的服务器， 第 i 个服务器拥有  ai 的贷款， 有  m 个顾客来租服务器，第 i 位顾客需要带宽至少 bi 得带宽，
 *   并且愿意花 ci 元 作为预算，服务器带宽独立不可叠加，若不能成功租出去，则输出0 ，小A可以选择拒绝一些人，现在小A 想知道
 *   自己的服务器最多能租到多少钱
 *
 *  输入描述 ：
 *     输入第一行包含两个数 n m
 *     接下来 1 行  n 个数，第 i 个数代表 第 i 台服务器的 带宽
 *     接下来 m 行，每行两个数 bi, ci ,表示 客户需求的带宽大小和他的预算
 *      n , m < 1000;  1 < ai,bi,ci < 1000
 *
 *  输出描述 ：
 *      输出一个数字，即小A 最多能租多少元的服务器出去
 *
 *
 * **/

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

public class fuWuqi {
    public static void main(String[] args) {
        Scanner scan =  new Scanner(System.in);
        String[] line1 =  scan.nextLine().split(" ");
        int n = Integer.parseInt(line1[0]);
        int m = Integer.parseInt(line1[1]);
        int[] computers  =  new int[n];
        String[] line2 = scan.nextLine().split(" ");
        for(int i=0;i<n;i++){
            computers[i] =  Integer.parseInt(line2[i]);
        }

        People[]  peoples = new People[m];
        for(int i=0;i<m;i++){
            String[] line3 =  scan.nextLine().split(" ");
            int need =  Integer.parseInt(line3[0]);
            int money =  Integer.parseInt(line3[1]);
            peoples[i] =  new People(need,money);
        }
        scan.close();
        // 排序，出钱多的排在前面，出钱一样多的，需要带宽小的排在前面
        Arrays.sort(peoples, new Comparator<People>() {
            @Override
            public int compare(People p1, People p2) {
                if(p1.money > p2.money ){
                    return -1;
                }else if(p1.money < p2.money){
                    return 1;
                }else {
                    return  p1.need- p2.need;
                }
            }
        });
        int sum =  0 ;
        boolean[] tag = new boolean[n];
        for(People people : peoples ){// 逐个客户来满足
            int need = people.need;
            int index = -1;
            for(int i=0;i<n;i++){
                if(tag[i]) continue;
                if(computers[i] >= need  && !tag[i]){
                    if(index == -1 ){ index = i;
                    }else{
                        if(computers[i] < computers[index])index = i;
                    }
                }
            }
            if(index != -1 ){
                tag[index] =  true;
                sum += people.money;
            }
        }
        System.out.println("可以获得的最大钱数为 ：  "+sum);
    }
}

class People{
    int need;
    int money;
    public People(int need,int money){
        this.need =  need;
        this.money = money;
    }
}