1 条题解
-
0
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
- 上传者