栈（括号匹配，机器人相撞）_n个机器人在数轴上,碰撞后运行方向相反

一、括号匹配

键入括号序列，文本框初始为空白，随即进行N次操作：

1. L:光标向前移动一个字符，（光标前没有字符则保持不动）（左移）

2. R:光标向后移动一个字符，（光标后没有字符则保持不动）（右移）

3. D:删除光标前的字符（光标前没有字符则保持不动）

4. ‘（’ 或 ‘）’：键入括号

评分标准：

1. 如果括号序列合法，得分为括号最大嵌套深度。

2. 如果括号序列不合法，得分为-x，x为使得该序列合法需要插入的最少括号字符个数。

输入 

第一行 操作数 整数 N

第二行 长度为N字符串，每个字符代表一次操作，字符均合法；

输出：一行，空格隔开N个整数，第i个整数，代表第i次操作后的实时分数。

输入

4

（）DD

输出

-1 1 -1 0

分析：leecode921,20,1111融合一起 括号的有效性判断+括号的最大深度+有效的最小添加

不能一轮完成，因为涉及回退等，每回操作完的序列，经上述三步操作完成。

第一个为参考答案，第二个自己微改的
 

package zsh;
import java.util.*;
 
public class Brackets {
    //判断是否有效括号
    public static boolean isValid(List<Character> list){
        Deque<Character> stack = new LinkedList<Character>();
        for(char c : list){
            if(c == '('){
                stack.push(c);
            }
            else {
                if(stack.isEmpty()){
                    return false;
                }
                if(stack.peek() == '('){
                    stack.pop();
                }
                else{
                    return false;
                }
            }
        }
        if(stack.isEmpty()){
            return true;
        }
        return false;
    }
    //括号嵌套深度
    public static int maxDepth(List<Character> list){
        int depth = 0;
        int maxDepth = 0;
        for(char c : list){
            if(c == '('){
                depth++;
                maxDepth = Math.max(maxDepth, depth);
            }
            else {
                depth--;
            }
        }
        return maxDepth;
    }
    //差几个使之有效
    public static int makeValid(List<Character> list){  //平衡法
        int left = 0;   //正向匹配，如（（（）
        int right = 0;  // 匹配 ））（，记录）数量
        for(char c : list){
            if(c == '('){
                left++;
            }
            else{
                left--;
            }
            if(left < 0){
                left++;
                right++;
            }
        }
        return -(left+right);
    }
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int optionNum = Integer.valueOf(scanner.nextLine());
        String s = scanner.nextLine();
        int cur = 0;  //光标位置
        List<Integer> score = new ArrayList<Integer>();
        List<Character> list = new ArrayList<Character>();
        for(Character c : s.toCharArray()){
            switch(c){
                case 'L':  //后退
                    if(cur > 0){
                        cur--;
                    }
                    break;
                case 'R':  //前进
                    if(cur < list.size()){
                        cur++;
                    }
                    break;
                case 'D':
                    if(!list.isEmpty()){
                        list.remove(cur-1);
                        cur--;
                    }
                    break;
                case '(':
                    list.add(cur, c);
                    cur++;
                    break;
                case ')':
                    list.add(cur, c);
                    cur++;
                    break;
            }
            if(isValid(list)){
                score.add(maxDepth(list));
            }
            else{
                score.add(makeValid(list));
            }
        }
        for(int i = 0; i < optionNum; i++){
            System.out.print(score.get(i));
            if(i != optionNum-1){
                System.out.print(" ");
            }
        }
    }
}

二、机器人相撞

题意：n个机器人在同一数轴上,有的往左走有的往右走,
同一时间在同一个整数点的机器人爆炸，
题解：（和括号匹配相似）
1.按位置排序(离得进的先撞，用栈)
2.分奇数偶数讨论，因为奇数和偶数之间不会爆炸

输入 第一行 机器人个数

其余行 机器人位置  方向

10
94 R
74 L
90 L
75 R
37 R
99 R
62 R
4 L
92 L
44 R

输出

-1 6 23 -1 -1 -1 6 -1 -1 23（竖着打印）

package zsh;
 
import java.util.*;
 
public class RobotCollision {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int total = Integer.parseInt(scanner.nextLine().trim());
        int[][] arr = new int[total][3];
        Deque<Integer> stack1 = new LinkedList<>();  //存奇数位置
        Deque<Integer> stack2 = new LinkedList<>();  //存偶数位置
        int num = 0;
        for(int i = 0; i < total; i++){
            arr[i][0] = scanner.nextInt();  //数轴位置
            arr[i][1] = scanner.next().equals("L") ? -1 : 1;  //左 -1 右 1
            arr[i][2] = num++;  //数轴次序
        }
        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
 
        int[] res = new int[total];
        Arrays.fill(res, -1);
        for(int i = 0; i < total; i++){
            if(arr[i][0] % 2 == 1) {  //奇数和奇数才能相撞，奇数和偶数不能相撞
                if (arr[i][1] == -1) {
                    if (stack1.isEmpty() || arr[stack1.peek()][1] == -1) {
                        stack1.push(i);
                    } else {
                        int j = stack1.pop();
                        res[arr[i][2]] = res[arr[j][2]] = (arr[i][0] - arr[j][0]) / 2;
                    }
                } else {
                    stack1.push(i);
                }
            }
            else{
                if (arr[i][1] == -1) {
                    if (stack2.isEmpty() || arr[stack2.peek()][1] == -1) {
                        stack2.push(i);
                    } else {
                        int j = stack2.pop();
                        res[arr[i][2]] = res[arr[j][2]] = (arr[i][0] - arr[j][0]) / 2;
                    }
                } else {
                    stack2.push(i);
                }
            }
        }
        for(int k : res){
            System.out.println(k);
        }
    }
}

参考 1525C - Robot Collisions https://codeforces.com/contest/1525/problem/C

https://blog.csdn.net/zhangx0710/article/details/117003988?utm_medium=distribute.pc_relevant.none-task-blog-2~default~baidujs_title~default-0.control&spm=1001.2101.3001.4242

/*
题意：n个机器人,有的往左走有的往右走,
同一时间在同一个整数点的机器人爆炸，
碰到墙改变方向
题解：
1.按位置排序
2.分奇数偶数讨论，因为奇数和偶数之间不会爆炸
3.如果一个向左的机器人，在左端没有其他相同奇偶性的点存在的情况下必然与右端相撞
4.左扫一次右扫一次
p.s. 学会
int i=vc.back() 最后一个元素
vc.pop_back() 弹出最后一个元素
*/
 
#include<bits/stdc++.h>
using namespace std;
#define x first.first
#define y first.second
#define z second
int T,n,m;
char c;
int main(){
    cin>>T;
    while(T--){
        
        cin>>n>>m;
        vector<pair<pair<int,int>,int>>a(n);
        for(int i=0;i<n;i++){
            cin>>a[i].x;
        }
        for(int i=0;i<n;i++){
            cin>>c;
            a[i].y=(c=='L'? -1:1);
            a[i].z=i;
        }
        sort(a.begin(),a.end());
 
        vector<int>ans(n,-1);
        vector<vector<int>>p(2);
 
        for(int i=0;i<n;i++){
            int r=a[i].x%2;
            if(a[i].y==-1){
                if(p[r].empty()){
                    p[r].push_back(i);
                }
                else {
                    int j=p[r].back();
                    p[r].pop_back();
                    ans[a[i].z] = ans[a[j].z] = (a[i].x - (a[j].y == 1 ? a[j].x : -a[j].x)) / 2;  
                   //y=1,一个回合左右相向相撞; y=-1, 左左转向第二回合相撞
                }
            }else{
                p[r].push_back(i);  //存的是右向，消除左向
            }
        }
 
        for(int r=0;r<2;r++){  //剩下的是右右 和 左向在右，右向在左情况
            while(p[r].size()>1){
                int i=p[r].back();
                p[r].pop_back();
                int j=p[r].back();
                p[r].pop_back();
                ans[a[i].z]=ans[a[j].z]=(2*m-a[i].x-(a[j].y==1?a[j].x:-a[j].x))/2;  
                //y=1,同右向；y = -1,左向在右，右向在左，第二回合相遇
 
            }
        }
 
        for(int i=0;i<n;i++){
            cout<<ans[i]<<' ';
        }
        cout<<endl;
    }
}