1 条题解

  • 0
    @ 2025-7-1 22:47:51

    JAVA题解:

    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));
            int n = Integer.parseInt(br.readLine());
            List<int[]> db = new ArrayList<>();
            
            for (int i = 0; i < n; i++) {
                String line = br.readLine();
                boolean isUndo = line.startsWith("undo");
                
                String data;
                if (isUndo) {
                    int idx = line.indexOf(' ', 5); // "undo algorithm "的长度
                    data = line.substring(idx + 1);
                } else {
                    data = line.substring(line.indexOf(' ') + 1);
                }
                
                List<int[]> segs = parse(data);
                
                if (isUndo) {
                    if (!db.isEmpty()) {
                        db = subtractIntervals(db, segs);
                    }
                } else {
                    db.addAll(segs);
                    db = mergeIntervals(db);
                }
            }
            
            // 输出结果
            if (db.isEmpty()) {
                System.out.print("0");
            } else {
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < db.size(); i++) {
                    int[] seg = db.get(i);
                    if (i > 0) sb.append(',');
                    if (seg[0] == seg[1]) {
                        sb.append(seg[0]);
                    } else {
                        sb.append(seg[0]).append('-').append(seg[1]);
                    }
                }
                System.out.print(sb.toString());
            }
        }
    
        // 解析方法
        static List<int[]> parse(String data) {
            String[] tokens = data.split(",");
            List<int[]> res = new ArrayList<>(tokens.length);
            
            for (String token : tokens) {
                int dashIndex = token.indexOf('-');
                if (dashIndex != -1) {
                    int start = Integer.parseInt(token.substring(0, dashIndex));
                    int end = Integer.parseInt(token.substring(dashIndex + 1));
                    res.add(new int[]{start, end});
                } else {
                    int x = Integer.parseInt(token);
                    res.add(new int[]{x, x});
                }
            }
            return res;
        }
    
        // 合并区间
        static List<int[]> mergeIntervals(List<int[]> intervals) {
            if (intervals.isEmpty()) return new ArrayList<>();
            
            // 对区间按起始位置排序
            intervals.sort(Comparator.comparingInt(a -> a[0]));
            
            List<int[]> result = new ArrayList<>();
            int l = intervals.get(0)[0];
            int r = intervals.get(0)[1];
            
            for (int i = 1; i < intervals.size(); i++) {
                int[] next = intervals.get(i);
                if (r + 1 < next[0]) {
                    result.add(new int[]{l, r});
                    l = next[0];
                    r = next[1];
                } else {
                    r = Math.max(r, next[1]);
                }
            }
            result.add(new int[]{l, r});
            
            return result;
        }
    
        // 从区间集合中删除指定区间
        static List<int[]> subtractIntervals(List<int[]> intervals, List<int[]> toRemove) {
            List<int[]> current = new ArrayList<>(intervals);
            
            for (int[] remove : toRemove) {
                int dl = remove[0];
                int dr = remove[1];
                List<int[]> temp = new ArrayList<>();
                
                for (int[] interval : current) {
                    int l = interval[0];
                    int r = interval[1];
                    
                    // 不重叠
                    if (r < dl || dr < l) {
                        temp.add(interval);
                    } else {
                        // 左侧剩余
                        if (l < dl) {
                            temp.add(new int[]{l, dl - 1});
                        }
                        
                        // 右侧剩余
                        if (dr < r) {
                            temp.add(new int[]{dr + 1, r});
                        }
                    }
                }
                
                current = temp;
            }
            
            return mergeIntervals(current);
        }
    }
    
    
    
    • 1

    信息

    ID
    12
    时间
    1000ms
    内存
    256MiB
    难度
    5
    标签
    递交数
    5
    已通过
    1
    上传者