贝壳笔试:多米诺骨牌-越界一直没处理出来
import java.util.*; public class 多米诺骨牌 { static class Node implements Comparable{ private int x; private int h; private int cnt; private int ans; private int max; public Node(int x, int h, int cnt, int ans, int max) { this.x = x; this.h = h; this.cnt = cnt; this.ans = ans; this.max = max; } @Override] public int compareTo(Node node) { return this.x - node.x; } } static class cmpCnt implements Comparator { @Override] public int compare(Node o1, Node o2) { return o1.cnt - o2.cnt; } } public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = Integer.parseInt(in.nextLine()); List list = new ArrayList(); for (int i = 0; i < n; i++) { String[] strs = in.nextLine().split(" "); int x = Integer.parseInt(strs[0]); int h = Integer.parseInt(strs[1]); int cnt = i; int ans = 1; int max = x + (h - 1); Node temp = new Node(x, h, cnt, ans, max); list.add(temp); } //处理越界用的Node Node temp = new Node(0, 0, 0, 0, 0); list.add(temp); Collections.sort(list); for (int i = n - 1; i >= 1; i--) { int j = i + 1; int max = list.get(i).max; while (j <= n && list.get(j).x <= max){ list.get(i).ans += list.get(j).ans; max = Math.max(max, list.get(j).max); j += list.get(j).ans; } list.get(i).max = max; } Collections.sort(list,new cmpCnt()); System.out.println(); for (int i = 1; i < n; i++) { System.out.print(list.get(i).ans + " "); } System.out.print(list.get(n).ans); } }
没有多余的测试用例,也不知道对错.
考完了照着大佬的改了下。
#贝壳找房#