AcWing 802. 区间和 Java版本 + 代码详解🎅

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 802. 区间和 Java版本 + 代码详解🎅 原题链接简单

作者：

Parrie , 2019-12-28 21:40:05 , 所有人可见 , 阅读 6184

56

30

心得

步骤比较多，但思路并不复杂
代码注释如下，欢迎小伙伴们交流
单方面宣布此题为第一章最难题👴

big O: $O(Nlog(N))$

Java 代码

import java.util.*;

public class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); //n次操作
        int m = sc.nextInt(); //m次询问
        int N = 300010; //因为需要将所有x，l，r存在数组中，这样就是n + 2m <= 300000
        int[] a = new int[N]; //从1开始，需要通过x找到离散量，然后+1，
        int[] s = new int[N]; //前缀和来做，所以需要从1开始记录a

        List<Integer> alls = new ArrayList<>(); //将所有的使用到的数存在alls中，比如x，l，r
        //但其中会有先后顺序的差别，以及重复，所以需要排序和去重
        List<Pairs> add = new ArrayList<>(); //用来存n次操作
        List<Pairs> query = new ArrayList<>(); //用来存m次询问

        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            int c = sc.nextInt();
            add.add(new Pairs(x, c));
            alls.add(x); //存入alls中，为后续操作做准备
        }

        for (int i = 0; i < m; i++) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            query.add(new Pairs(l, r));
            alls.add(l);
            alls.add(r);
        }
        //到此为止，alls中存好了所有会被用到的数轴上的点，可以进行离散化操作
        // 1. 排序 2. 去重
        Collections.sort(alls);
        int unique = unique(alls);
        alls = alls.subList(0, unique); //将去重后的List保存下来，或者此处也可以将unique作为最后一个数，用r作为二分

        for (Pairs item:add) {
            int index = find(item.first, alls);
            a[index] += item.second;
        }

        //求前缀和
        for (int i = 1; i <= alls.size(); i++) s[i] = s[i - 1] + a[i];

        for (Pairs item:query) {
            int l = find(item.first, alls);
            int r = find(item.second, alls);
            System.out.println(s[r] - s[l - 1]);
        }
    }

    //去重
    static int unique(List<Integer> list) {
        int j = 0;
        for (int i = 0; i < list.size(); i++) {
            if (i == 0 || list.get(i) != list.get(i - 1)) {
                list.set(j, list.get(i));
                j++;
            }  
        }
        return j;
    } 

    static int find(int x, List<Integer> list) {
        int l = 0;
        int r = list.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (list.get(mid) >= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l + 1; //因为要考虑到前缀和
    }
}

class Pairs {
    int first;
    int second;
    public Pairs(int first, int second) {
        this.first = first;
        this.second = second;
    }
}

大家圣诞快乐🎄！

38 评论

acvv_motibodo 2022-04-30 13:21

unique + sort的功能可以通过HashSet 两行代码去实现更简单：
alls = new ArrayList<>(new HashSet<>(alls));
Collections.sort(alls);

世蒂 2022-07-30 23:16

想的一样

dogdie 7个月前

Main.java:50: error: non-static variable this cannot be referenced from a static context
k.add(new Pairs(l , r));
^
Main.java:59: error: non-static variable this cannot be referenced from a static context
f.add(new Pairs(l , r));
哪个大佬可以帮我看看，为什么会出现这个问题

王振兴 2022-04-13 17:01

去重代码错了，没有实现去重效果，只是碰巧用二分去查，返回结果是对的。list.get(i) != list.get(i - 1)应该用equals比较。

是西红柿不是番茄 2022-04-29 13:55

为什么呀?能细说一下吗?

王振兴 2022-05-04 15:31 回复了是西红柿不是番茄的评论

Integer包装类比较用equals()，你可以了解一下==和equals()的区别

吾乃闪耀の芝士蛋挞 7个月前回复了王振兴的评论

准确说是不在中的cache -128~127 中的数用 == 是错误的，应该用equals()

腼腆的CodeMedicine 2021-11-05 21:58

TreeMap,有序+查找
~红黑树

@思无邪 2021-10-30 12:29

个人想法：
总体思路就是讲用到的所有下标排序，然后下标的值也按对应顺序存放在另一个数组中
如：list = 3,5,7,9
a = 1,0,8,7
表示的是3位置存放的数是1,5位置存放的数是0,7位置存放的数是8,9位置存放的数是7

shenwanqin 7个月前

import java.util.*;
public class Main{
static class Pairs{
int first;
int second;
public Pairs(int first,int second){
this.first = first;
this.second = second;
}
}

public static int find(int x,List<Integer> all){
    int l = 0;
    int r = all.size()-1;
    //Integer []alls = all.toArray(new Integer[all.size()]);
    while(l<r){
        int mid = l+r>>1;
        if(all.get(mid)>=x) r = mid;
        else l = mid+1;
    }
    return r+1;   //下标从1开始
}
public static void main(String []args){
    Scanner scanner  = new Scanner(System.in);
    int n = scanner.nextInt();
    int m = scanner.nextInt();
    int N = 300010;
    int []a = new int[N];
    int []s = new int[N];
    List<Integer> all = new ArrayList<>();
    List<Pairs> add = new ArrayList<>();
    List<Pairs> query = new ArrayList<>();
    for(int i = 0;i<n;i++){
        int x = scanner.nextInt();
        int c = scanner.nextInt();
        add.add(new Pairs(x,c));
        all.add(x);
    }

    for(int i = 0;i<m;i++){
        int l = scanner.nextInt();
        int r = scanner.nextInt();
        query.add(new Pairs(l,r));
        all.add(l);
        all.add(r);
    }

    all = new ArrayList(new TreeSet<>(all));    //去重 + 排序
    for(Pairs item:add){  
        int index = find(item.first,all);
        a[index] += item.second;
    }
    for(int i = 1;i<=all.size();i++){
        s[i] = s[i-1] + a[i];
    }

    for(Pairs item:query){
        int l = find(item.first,all);
        int r = find(item.second,all);
        System.out.println((s[r]-s[l-1]));
    }
}

}
利用TreeSet进行去重排序

Solitude._4 2023-07-20 16:40

Exception in thread “main” java.util.InputMismatchException
at java.base/java.util.Scanner.throwFor(Scanner.java:939)
at java.base/java.util.Scanner.next(Scanner.java:1594)
at java.base/java.util.Scanner.nextInt(Scanner.java:2258)
at java.base/java.util.Scanner.nextInt(Scanner.java:2212)
at Main.main(Main.java:19)