题目描述 Alternative Cake Manufacturing（ACM）有n名员工。他们现在就一些非常重要的问题进行投票，世界主要媒体正试图预测投票结果。每个雇员都属于两个部分中的一个：D队或R队，这两个部分对投票结果有相反的意见。投票程序相当复杂：n名雇员中的每一名都发表声明。他们从雇员1开始逐一发表声明，并以雇员n结束。如果在第i名雇员发表声明的时刻，他可以选择一名雇员使其无法进行投票(被选择的雇员将被取消投票). 一轮结束后，如果具有投票资格的人数大于1，则重复上述操作，直到只有一名员工有资格投票，并确定整个投票的结果。当然，他投票支持他所在的队伍。您知道雇员将要投票的结果以及他们的最佳选择，请预测投票结果。 输入 输入的第一行包含一个整数n（1≤n≤200000） - 员工人数。下一行包含n个字符。如果第i个雇员来自D队，那么第i个字符是'D'，如果他来自R队，则是'R'。 输出 打印'D'如果投票结果为D队将获胜，'R'如果R队将获胜。 样例输入 Copy 5 DDRRR 样例输出 Copy D 提示 考虑样例的投票场景之一：员工1禁止员工5投票。员工2禁止员工3投票。员工3无权投票并跳过他（员工2禁止了他）。员工4禁止员工2投票。员工5无权投票并跳过他（员工1禁止了他）。员工1禁止员工投票。 只有员工1现在才有投票权，因此投票以’D'的胜利结束。请用Java代码实现，并附带解析

题目分析：

这道题是一道模拟题，需要我们模拟整个投票过程，以确定最终的投票结果。我们可以使用一个队列来模拟投票过程。队列中存储的是有资格投票的员工的编号，每次从队列中取出队头元素，然后遍历队列中的其他元素，找到一个可以取消投票的人，将其从队列中删除。如果队列中只剩下一个人，则投票结束，输出该人所在的队伍即可。

Java代码实现：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next();
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            q.offer(i);
        }
        while (q.size() > 1) {
            int x = q.poll();
            int y = -1;
            for (int i = 0; i < q.size(); i++) {
                int t = q.poll();
                if (s.charAt(t) != s.charAt(x)) {
                    y = t;
                    break;
                }
                q.offer(t);
            }
            if (y != -1) {
                q.offer(y);
            }
        }
        System.out.println(s.charAt(q.poll()) == 'D' ? "D" : "R");
    }
}

时间复杂度：$O(n^2)$

空间复杂度：$O(n)$

优化：

上述代码的时间复杂度很高，因为每一轮都需要遍历队列中的所有元素，导致总时间复杂度为$O(n^2)$。我们可以使用一个数组来记录每个人的下一个可以投票的人的编号，这样每一轮就只需要遍历一遍数组，就可以找到下一个可以投票的人，大大降低了时间复杂度。

Java代码实现：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next();
        int[] next = new int[n];
        for (int i = 0; i < n; i++) {
            next[i] = (i + 1) % n;
        }
        for (int i = 0; i < n - 1; i++) {
            int x = i;
            while (next[x] != x) {
                int y = next[x];
                if (s.charAt(y) != s.charAt(x)) {
                    next[x] = next[y];
                    break;
                }
                x = next[x];
            }
        }
        System.out.println(s.charAt(next[0]) == 'D' ? "D" : "R");
    }
}

时间复杂度：$O(n)$

空间复杂度：$O(n)$