AcWing
  • 首页
  • 活动
  • 题库
  • 竞赛
  • 校园
  • 应用
  • 文章
    • 题解
    • 分享
    • 问答
  • 吐槽
  • 登录/注册

AcWing 802. 「Java」TreeMap 模拟二分    原题链接    简单

作者: 作者的头像   f@ck1ngCumm1ng ,  2022-06-24 09:20:52 ,  所有人可见 ,  阅读 10


1


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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
        String[] nk = sc.readLine().split(" ");
        int n = Integer.parseInt(nk[0]);
        int m = Integer.parseInt(nk[1]);
        TreeMap<Integer, Integer> map = new TreeMap<>();
        while (n-- > 0) {
            int[] xc = Arrays.stream(sc.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            map.put(xc[0], map.getOrDefault(xc[0], 0) + xc[1]);
        }
        int prev = 0;
        int minK = Integer.MAX_VALUE;
        int maxK = Integer.MIN_VALUE;
        for (Map.Entry<Integer, Integer> e : map.entrySet()) {
            minK = Math.min(e.getKey(), minK);
            maxK = Math.max(e.getKey(), maxK);
            int v = e.getValue();
            e.setValue(v + prev);
            prev += v;
        }
        for (int i = 0; i < m; i++) {
            int[] lr = Arrays.stream(sc.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

            Map.Entry<Integer, Integer> t1 = map.lowerEntry(lr[0]);
            Map.Entry<Integer, Integer> t2 = map.floorEntry(lr[1]);
            int left = t1 == null ? 0 : t1.getValue();
            int right = t2 == null ? map.get(maxK) : t2.getValue();
            System.out.println(right - left);
        }
    }
}

0 评论

你确定删除吗?

© 2018-2022 AcWing 版权所有  |  京ICP备17053197号-1
用户协议  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息