1. ac 看着描述复杂,实际访问顺序已经被题目定死了,按输入指定的优先级排序即可,纯模拟。整体复杂度O(n*log(n))
细节:景点第几天访问可以在O(1)时间内算出来,公式:((当前日期 - 最早日期)/ 每次延期天数)向下取整后 + 1) * 每次延期天数 + 最早日期
2. ac 优先队列,最短剩余时间优先,剩余时间相同最早布置优先。整体复杂度O(n*log(n))
public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int[][] task = new int[n][2]; for (int i = 0; i < n; i++) { for (int j = 0; j < 2; j++) { task[i][j] = in.nextInt(); } } PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (a[1] == b[1] ? a[0] - b[0] : a[1] - b[1])); long ans = 0, cur = 0; // cur表示当前时间 for (int i = 0; i < n - 1; i++) { cur = task[i][0]; pq.offer(task[i]); int interval = task[i + 1][0] - task[i][0]; // 距离下一项作业被布置的时间 while (interval > 0 && !pq.isEmpty()) { int[] t = pq.peek(); if (interval >= t[1]) { pq.poll(); cur += t[1]; ans += (cur - t[0]); interval -= t[1]; } else { t[1] -= interval; interval = 0; } } } cur = task[n - 1][0]; pq.offer(task[n - 1]); while (!pq.isEmpty()) { int[] t = pq.poll(); cur += t[1]; ans += (cur - t[0]); } System.out.println(ans); }
3. ac 核心的两点:
① 观赏度的奇偶性永远不变,要么永远奇数,要么永远偶数
② 假设观赏度能取负数(不取绝对值),有这样一个结论:如果能取到的最大观赏度为mx,最小观赏度为mn,那么mx和mn之间的每个观赏度都能取到。严谨证明我没想过,但是从我ac了来看这个结论没问题
于是,题目转化为求最大观赏度和最小观赏度。然后就完全变成了“最大子数组和”问题。整体复杂度O(n)
public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int curMaxSum = 0, curMinSum = 0; int maxSum = 0, minSum = 0; int totalSum = 0; for (int i = 0; i < n; i++) { int a = (in.nextInt() == 1 ? 1 : -1); totalSum += a; curMinSum = Math.min(curMinSum + a, a); minSum = Math.min(minSum, curMinSum); curMaxSum = Math.max(curMaxSum + a, a); maxSum = Math.max(maxSum, curMaxSum); } int minScore = totalSum - 2 * maxSum; int maxScore = totalSum - 2 * minSum; int ans = 0; if ((long) maxScore * minScore <= 0) { // 最大最小观赏度是否同侧 分类讨论 ans = Math.max(Math.abs(maxScore), Math.abs(minScore)) / 2 + 1; } else { ans = Math.abs(maxScore - minScore) / 2 + 1; } System.out.println(ans); }
4. 72%tle 转化为有向图。对于每个位置,从“线性探测时跨越的位置”到“最终位置”各连一条有向边。然后拓扑排序,排序顺序就是答案。对于字典序问题,把拓扑排序中的队列换成优先队列就行了。
但这样做最坏情况整体复杂度会达到O(n^2),所以tle了,希望ac的朋友们分享下解法
全部评论
(9) 回帖