首页 > 8.26阿里笔试第二题
头像
offer与我同在
编辑于 2020-08-26 10:11
+ 关注

8.26阿里笔试第二题

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int T = sc.nextInt();
    while(T-- > 0) {
        int n = sc.nextInt();//怪物
        int m = sc.nextInt();//耐久度
        int[][] arr = new int[n][2];
        for(int i = 0; i < n; i++) {
            arr[i][0] = sc.nextInt();//消耗耐久度
            arr[i][1] = sc.nextInt();//掉落武器数量
        }
        Arrays.sort(arr, new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) {
                return o1[0] == o2[0] ? o2[1] - o1[1] : o1[0] - o2[0];
            }
        });
        if(m < arr[0][0]) {
            System.out.print(0 + " ");
            System.out.println(0);
        } else {
            int can = arr[0][1];
            int resm = m - arr[0][0];
            int res = 1;
            int i = 1;
            for(; i < n; i++) {
                if(resm < arr[i][0] && can <= 0) break;
                if(can > 0) {
                    can = can - 1;
                } else {
                    resm = resm - arr[i][0];
                }
                can = can + arr[i][1];
            }
            resm = m - resm;
            System.out.print(i + " ");
            System.out.println(resm);
        }

    }
}
第二题还不及判题,本地测试是对的(可能用例不够),大伙看看是对吗?
思路:先对每件武器消耗耐久度按升序排列,耐久度相同就按掉落的武器数降序排列,最后使用贪心得出结果。

全部评论

(3) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐