Lintcode 1667.石头

全栈程序员站长

发布于 2022-09-15 11:30:43

1700

发布于 2022-09-15 11:30:43

文章被收录于专栏：全栈程序员必看

大家好，又见面了，我是你们的朋友全栈君。

题目大意：一条直线上有n个石头，一个人从左往右走，碰到奇数块石头（碰到一块石头数一个数，这里指数的数是奇数），就往右扔，碰到偶数的石头就不管他，如果两块石头在同一个位置，就扔大的那块（能扔的距离小的）。问最后最远的那块石头的位置。

思路：用优先队列模拟，每遇到奇数石头，就将其坐标加上D[i]，放回优先队列，当石头重叠时，先扔投大的（能扔的距离小的），故在比较函数中，以位置为第一关键字，以投掷距离为第二关键字。

class Node {
        int p;
        int d;
    }

    public int getDistance(int[] p, int[] d) {
        PriorityQueue<Node> priorityQueue = new PriorityQueue<>((o1, o2) -> {
            if (o1.p == o2.p) {
                return o1.d - o2.d;
            } else {
                return o1.p - o2.p;
            }
        });

        Node res = null;

        for (int i = 0; i < p.length; i++) {
            Node node = new Node();
            node.p = p[i];
            node.d = d[i];
            priorityQueue.add(node);
        }
        boolean temp = true;
        while (!priorityQueue.isEmpty()) {
            res = priorityQueue.remove();
            if (temp) {
                res.p = res.p + res.d;
                priorityQueue.add(res);
            }
            temp = !temp;
        }
        return res.p;
    }

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/163855.html原文链接：https://javaforall.cn

【正版授权，激活自己账号】： Jetbrains全系列IDE使用 1年只要46元售后保障童叟无欺

【官方授权正版激活】： 官方授权正版激活支持Jetbrains家族下所有IDE 使用个人JB账号...

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

ide