顺丰科技8.20笔试编程题

服务器管理 时间限制： 3000MS 内存限制： 786432KB 题目描述： 小A的购买了一批服务器，他准备将这些服务器租用出去。 每一个服务器有一个固定的带宽，人们根据自己需要的带宽来租用这些服务器。一台服务器只能租给一个人。  小A现在有n个空闲的服务器，第 i 个服务器拥有ai的带宽。 有m个客户来租服务器，第 i 位客户需要带宽至少为bi的服务器，并且愿意花ci元作为预算。 （服务器带宽独立不可叠加，若不能成功租出则输出0） 
小A可以选择拒绝一些人，现在，小A想知道自己的服务器最多能租多少钱？  输入描述 输入第一行包含两个数n,m  接下来1行n个数，第i个数ai代表第 i 个服务器的带宽大小。  接下来m行，每行两个数bi,ci，代表客户需求的带宽大小和他的预算。  n,m≤1000 , 1≤ai,bi,ci≤1000 输出描述 输出一个数，即小A最多能租多少元的服务器出去。

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        String[] strs;
        line = br.readLine();
        strs = line.split(" ");
        //服务器数量n
        int n = Integer.parseInt(strs[0]);
        int[] serves = new int[n];
        //客户数量m
        int m = Integer.parseInt(strs[1]);
        int[][] cons = new int[m][2];
        line = br.readLine();
        strs = line.split(" ");
        for (int i = 0; i < n; i++) {
            serves[i] = Integer.parseInt(strs[i]);
        }
        for (int i = 0; i < m; i++) {
            line = br.readLine();
            strs = line.split(" ");
            cons[i][0] = Integer.parseInt(strs[0]);
            cons[i][1] = Integer.parseInt(strs[1]);
        }
        Arrays.sort(serves);
        Arrays.sort(cons, Comparator.comparingInt(a -> a[0]));
        int index_s = 0;
        int index_c = 0;
        int res = 0;
        List<Integer> arr = new ArrayList<>();
        while (index_s < n && index_c < m) {
            int tmp = cons[index_c][0];
            //服务器带宽先符合要求
            while (index_s < n && serves[index_s] < tmp) {
                index_s++;
            }
            int count = 0;
            //计算这个带宽的客户数量
            while (index_c < m && cons[index_c][0] == tmp) {
                arr.add(cons[index_c][1]);
                index_c++;
            }
            //下一个带宽要求
            if (index_c < m) {
                tmp = cons[index_c][0];
                //计算满足带宽的服务器数量
                while (index_s < n && serves[index_s] < tmp) {
                    count++;
                    index_s++;
                }
            }else{
                while (index_s < n ) {
                    count++;
                    index_s++;
                }
            }
            //记录客户对应的价格
            int[] tmps = new int[arr.size()];
            for (int i = 0; i < arr.size(); i++) {
                tmps[i] = arr.get(i);
            }
            Arrays.sort(tmps);
            int index = tmps.length - 1;
            //服务器不够或者客户不够 退出循环
            while (index >= 0 && count > 0) {
                res += tmps[index];
                index--;
                count--;
            }
            //如果还有余下的客户,更新arr
            arr = new ArrayList<>();
            while (index >= 0) {
                arr.add(tmps[index]);
                index--;
            }
            //这个时候指针s与c分别指向后面
        }
        System.out.println(res);
    }
}

赏金猎人 时间限制： 3000MS 内存限制： 786432KB 题目描述： 克里森是一名赏金猎人，他平时需要完成一些任务赚钱。最近他收到了一批任务， 但是受到时间的限制，他只能完成其中一部分。
    具体来说就是有n个任务，每个任务用l, r, w来表示任务开始的时间l， 结束的时间r和完成任务获得的金钱。 克里森是个贪心的人，他想知道自己在任务不冲突的情况下最多获得多少金钱。 输入描述 第一行一个数n表示任务的个数。(1≤n≤1e3)  接下来n行每行三个整数l, r, w表示第i个任务的开始时间，结束时间，以及收益。(1≤l≤r≤1e6,1≤w≤1e9)  输出描述 输出一个值表示克里森最多获得的金钱数量。

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        String[] strs;
        //任务数量n
        int n = Integer.parseInt(br.readLine());
        int[][] nums = new int[n][3];
        //读取后面
        for (int i = 0; i < n; i++) {
            line = br.readLine();
            strs = line.split(" ");
            //开始
            nums[i][0] = Integer.parseInt(strs[0]);
            //结束
            nums[i][1] = Integer.parseInt(strs[1]);
            //赏金
            nums[i][2] = Integer.parseInt(strs[2]);
        }
        Arrays.sort(nums, Comparator.comparingInt(a -> a[0]));

        long[] res = new long[n];
        int end = nums[n - 1][0];
        long ans = 0;
        for (int i = n - 1; i >= 0; i--) {
            //如果结束时间超过最后一个任务的开始时间 直接记录赏金
            if (nums[i][1] > end) res[i] = nums[i][2];
            else {
                //当前任务的结束时间
                int r = nums[i][1];
                long max = 0;
                for (int j = i + 1; j < n; j++) {
                    //开始时间大于结束时间的
                    if (nums[j][0] > r) {
                        max = Math.max(max, res[j]);
                    }
                }
                //记录当前格的赏金
                res[i] = nums[i][2]+max;
                ans = Math.max(ans,res[i]);
            }
        }
        System.out.println(ans);
    }
}