传送讯息

Question

我有一项任务要解决这个问题。

问题描述

鲍勃猫正在建设一个新的系统，称为猫传输系统(CTS)。这种效率极低的系统利用猫来帮助传输信息。在这个系统中，有N个猫排在从cat 0到cat N1的一条线上。如果需要将消息从cat 2传输到cat 7，则cat 2将把消息传递给cat 3，传递给cat 4.依此类推，直到它到达第七猫。听起来很简单，对吧？然而，存在一个问题。众所周知，猫喜欢睡觉。这些猫中有些人在工作中往往会睡着。比如说，如果cat 3睡着了，从cat 2到cat 7的消息将无法传输。因此，给出了“睡眠”和“唤醒”事件的列表，以及中间的“传输”请求，Bob希望您检查这些“传输”请求是否会通过。所有的猫都醒着。将会有一系列的Q事件。事件的格式如下:输入第一行输入将包含两个整数，N和Q，下一行输入将包含上述一个事件。输出极限·0X试图将信息从Cat X传输到Cat 是。如果它是成功的(从X到是包含的所有猫都醒着)，那么输出“是”。否则，输出“否”。样本输入8 8发送2 7睡眠6发送1 7发送1 5睡眠4发送1 3唤醒4发送1 5样本输出是否共8猫，标记从0到7，以及接下来的8个事件。起初，8只猫都醒着。因此，从猫2到7的传输请求将成功。然后，猫6睡着了。随后，猫1到7的传输请求将失败，因为cat 5不能将信息传输到正在休眠的cat 6。然而，猫1到5的传输请求仍将成功，因为范围内的每一只猫都仍处于清醒状态。然后，猫4睡着了。猫1到3的下一次传输请求仍然成功，因为范围内的每一只猫都仍然醒着。第四猫现在醒了。猫1到5的传输请求将成功，因为范围内的每一只猫现在都醒了。

我尝试过使用TreeSet来解决这个问题(我之所以选择这个问题是因为它有点像一个双结束优先级队列，因此我的解决方案将在O(log n)中运行，但是由于某些原因，我仍然可以在我正在测试的平台上获得TimeLimitExceeded。我不知道的TreeSet有什么慢的地方吗?这里有什么更好的解决方案呢？

尝试

import java.util.*;


public class Transmission {
    private void run() {
        Scanner sc = new Scanner(System.in);
        int endIdx = sc.nextInt()-1;
        int cmdCount = sc.nextInt();
        TreeSet<Integer> dEndQueue = new TreeSet<>();

        for (int i=0;i< cmdCount;i++) {
            String cmd = sc.next();

            if (cmd.equals("TRANSMIT")) {
                int start = sc.nextInt();
                int end = sc.nextInt();

                if (dEndQueue.isEmpty()) {
                    System.out.println("YES");
                    continue;
                }

                Integer firstHole = dEndQueue.ceiling(start);
                if (firstHole==null || firstHole>end) {
                    System.out.println("YES");
                } else {
                    System.out.println("NO");
                }
            } else if (cmd.equals("SLEEP")) {
                int entry = sc.nextInt();
                dEndQueue.add(entry);
            } else if (cmd.equals("WAKE")) {
                int entry = sc.nextInt();
                dEndQueue.remove(entry);
            }

        }
    }
    public static void main(String[] args) {
        Transmission newTransmission = new Transmission();
        newTransmission.run();
    }

}

Answer 1

我建议您使用布尔数组(状态为N)，并将对应元素的值设置为true或false，并在每次调用发送命令时迭代该数组：

private static String keyWord;
private static int source;
private static int destination;
private static boolean[] states;


public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int q = sc.nextInt();
    sc.nextLine();
    String [] commands = new String[q];
    states = new boolean[n];
    for(int i=0; i<n; i++) {
        states[i]  =true;
    }
    String output = "";
    for(int i=0; i<q; i++) {
        commands[i] = sc.nextLine();
        output+=readCommand(commands[i]).length()!=0?readCommand(commands[i])+"\n":"";
    }
    System.out.println(output);
}

private static String readCommand(String command) {
    String[] words = command.split(" ");
    keyWord = words[0];
    source = Integer.parseInt(words[1]);
    if(keyWord.equals("SLEEP")) {
        states[source] = false;
        return"";
    }
    if(keyWord.equals("WAKE")) {
        states[source] = true;
        return "";
    }
    if(keyWord.equals("TRANSMIT")) {
        destination = Integer.parseInt(words[2]);
        return isTransmitted(source, destination);
    }
    return"";
}

private static String isTransmitted(int from, int to) {
    for(int i = from; i<=to; i++) {
        if(!states[i]) {
            return "NO";
        }
    }
    return "YES";
}

我希望这能帮到你。