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的朋友们分享下解法
点赞 8
评论 9
全部评论

相关推荐

湫湫湫不会java:先投着吧,大概率找不到实习,没实习的时候再加个项目,然后把个人评价和荣誉奖项删了,赶紧成为八股战神吧,没实习没学历,秋招机会估计不多,把握机会。或者说秋招时间去冲实习,春招冲offer,但是压力会比较大
点赞 评论 收藏
分享
牛客38347925...:9,2学生暑期实习失利开始投小厂,给这群人整自信了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务