题面描述

幼儿园里有一个放倒的圆桶，它是一个线性结构，允许在桶的右边将篮球放入，可以在桶的左边和右边将篮球取出。每个篮球有单独的编号，老师可以连续放入一个或多个篮球，小朋友可以在桶左边或右边将篮球取出，当桶只有一个篮球的情况下，必须从左边取出。

给定老师放入篮球的顺序和小朋友取出篮球的顺序，判断取出顺序是否可行。如果可行，输出相应的取出操作序列（用L表示从左取，R表示从右取）；否则，输出NO。

思路

这个问题可以使用双端队列（deque）来模拟桶的操作过程。具体步骤如下：

1. 初始化：

   • 使用一个双端队列bucket来表示桶内的篮球。
   • 使用两个指针，一个指向插入序列的当前插入位置（insert_ptr），一个指向移除序列的当前移除位置。

2. 模拟操作：

   • 对于移除序列中的每一个目标篮球target：
     • 插入阶段：不断将篮球从插入序列中放入桶的右侧，直到目标篮球target出现在桶的左端或右端。
     • 移除阶段：
       • 如果target在左端，执行L操作，将其从左端移出。
       • 如果target在右端，执行R操作，将其从右端移出。
       • 如果无法将target放到桶的两端，则输出NO，因为无法实现该移除顺序。

3. 特殊情况：

   • 当桶内只有一个篮球时，必须从左端移出。

4. 验证：

   • 最后检查所有篮球是否都按照指定顺序被移出。如果是，则输出对应的操作序列；否则，输出NO。

cpp

#include <bits/stdc++.h>
using namespace std;

// 分割字符串函数，将逗号分隔的字符串转换为整数向量
vector<int> split(const string& s) {
    vector<int> res;
    string num;
    for(char c : s){
        if(c == ',') {
            if(!num.empty()) {
                res.push_back(stoi(num));
                num.clear();
            }
        }
        else num += c;
    }
    if(!num.empty()) res.push_back(stoi(num));
    return res;
}

int main(){
    string insert_line, remove_line;
    // 读取放入序列
    getline(cin, insert_line);
    // 读取取出序列
    getline(cin, remove_line);
    
    vector<int> insert_seq = split(insert_line);
    vector<int> remove_seq = split(remove_line);
    
    // 检查移除序列长度是否超过插入序列
    if(remove_seq.size() > insert_seq.size()){
        cout << "NO";
        return 0;
    }
    
    deque<int> bucket; // 模拟桶的双端队列
    int insert_ptr = 0; // 插入序列的指针
    string ops = ""; // 记录操作序列
    
    for(auto target : remove_seq){
        // 插入篮球直到目标篮球位于桶的两端
        while( (bucket.empty() || (bucket.front() != target && bucket.back() != target)) ){
            if(insert_ptr >= insert_seq.size()){
                break; // 无法继续插入
            }
            bucket.push_back(insert_seq[insert_ptr++]);
        }
        // 特殊情况：桶内只有一个篮球，必须从左取
        if(bucket.size() == 1){
            if(bucket.front() == target){
                ops += "L";
                bucket.pop_front();
            }
            else{
                // 只有一个篮球，但不是目标篮球
                break;
            }
        }
        else{
            if(!bucket.empty()){
                if(bucket.front() == target){
                    ops += "L";
                    bucket.pop_front();
                }
                else if(bucket.back() == target){
                    ops += "R";
                    bucket.pop_back();
                }
                else{
                    // 目标篮球不在两端
                    break;
                }
            }
            else{
                // 桶为空，但还有篮球要取
                break;
            }
        }
    }
    
    // 检查是否所有篮球都被成功移除
    if(ops.size() == remove_seq.size()){
        cout << ops;
    }
    else{
        cout << "NO";
    }
}

python

from collections import deque
import sys

def split_line(s):
    return list(map(int, s.strip().split(',')))

def main():
    insert_line = sys.stdin.readline()
    remove_line = sys.stdin.readline()
    
    insert_seq = split_line(insert_line)
    remove_seq = split_line(remove_line)
    
    if len(remove_seq) > len(insert_seq):
        print("NO")
        return
    
    bucket = deque()
    insert_ptr = 0
    ops = []
    
    for target in remove_seq:
        # 插入篮球直到目标篮球位于桶的两端
        while (not bucket) or (target != bucket[0] and target != bucket[-1]):
            if insert_ptr >= len(insert_seq):
                break
            bucket.append(insert_seq[insert_ptr])
            insert_ptr += 1
        # 特殊情况：桶内只有一个篮球，必须从左取
        if len(bucket) == 1:
            if bucket[0] == target:
                ops.append('L')
                bucket.popleft()
            else:
                break
        else:
            if not bucket:
                break
            if bucket[0] == target:
                ops.append('L')
                bucket.popleft()
            elif bucket[-1] == target:
                ops.append('R')
                bucket.pop()
            else:
                break
    if len(ops) == len(remove_seq):
        print(''.join(ops))
    else:
        print("NO")

if __name__ == "__main__":
    main()

java

import java.util.*;
import java.io.*;

public class Main {
    // 分割字符串函数，将逗号分隔的字符串转换为整数列表
    public static List<Integer> splitLine(String s){
        List<Integer> res = new ArrayList<>();
        String[] parts = s.trim().split(",");
        for(String part : parts){
            if(!part.isEmpty()){
                res.add(Integer.parseInt(part));
            }
        }
        return res;
    }
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String insertLine = br.readLine();
        String removeLine = br.readLine();
        
        List<Integer> insertSeq = splitLine(insertLine);
        List<Integer> removeSeq = splitLine(removeLine);
        
        if(removeSeq.size() > insertSeq.size()){
            System.out.println("NO");
            return;
        }
        
        Deque<Integer> bucket = new LinkedList<>();
        int insertPtr = 0;
        StringBuilder ops = new StringBuilder();
        
        for(int target : removeSeq){
            // 插入篮球直到目标篮球位于桶的两端
            while( (bucket.isEmpty() || (bucket.peekFirst() != target && bucket.peekLast() != target)) ){
                if(insertPtr >= insertSeq.size()){
                    break;
                }
                bucket.addLast(insertSeq.get(insertPtr++));
            }
            // 特殊情况：桶内只有一个篮球，必须从左取
            if(bucket.size() == 1){
                if(bucket.peekFirst() == target){
                    ops.append("L");
                    bucket.pollFirst();
                }
                else{
                    break;
                }
            }
            else{
                if(!bucket.isEmpty()){
                    if(bucket.peekFirst() == target){
                        ops.append("L");
                        bucket.pollFirst();
                    }
                    else if(bucket.peekLast() == target){
                        ops.append("R");
                        bucket.pollLast();
                    }
                    else{
                        break;
                    }
                }
                else{
                    break;
                }
            }
        }
        
        if(ops.length() == removeSeq.size()){
            System.out.println(ops.toString());
        }
        else{
            System.out.println("NO");
        }
    }
}

题目内容

幼儿园里有一个放倒的圆桶，它是一个线性结构，允许在桶的右边将篮球放入，可以在桶的左边和右边将篮球取出。

每个篮球有单独的编号，老师可以连续放入一个或多个篮球，小朋友可以在桶左边或右边将篮球取出，当桶只有一个篮球的情况下，必须从左边取出。

如老师按顺序放入$1、2、3、4、5$共有 $5$ 个编号的篮球，那么小朋友可以依次取出编号为 $1、2、3、4、5$ 或者 $3、1、2、4、5$ 编号的篮球，无法取出 $5、1、3、2、4$ 编号的篮球。

其中 $3、1、2、4、5$ 的取出场景为：

• 连续放入 $1、2、3$ 号
• 从右边取出 $3$ 号
• 从左边取出 $1$ 号
• 从左边取出 $2$ 号
• 放入 $4$ 号
• 从左边取出 $4$ 号
• 放入 $5$ 号
• 从左边取出 $5$ 号

简答起见，我们以 $L$ 表示左，$R$ 表示右，此时取出篮球的依次取出序列为“$RLLLL$”。

输入描述

每次输入包含一个测试用例：

1. 第一行的数字作为老师依次放入的篮球编号
2. 第二行的数字作为要检查是否能够按照放入的顺序取出给定的篮球的编号，其中篮球的编号用逗号进行分隔。

其中篮球编号用逗号进行分隔。

输出描述

对于每个篮球的取出序列，如果确实可以获取，请打印出其按照左右方向的操作取出顺序，如果无法获取则打印“$NO$”。

备注

• $1 ≤$ 篮球编号，篮球个数 $≤ 200$
• 篮球上的数字不重复
• 输出的结果中 $LR$ 必须为大写

样例1

输入

4,5,6,7,0,1,2
6,4,0,1,2,5,7

输出

RLRRRLL

说明

篮球的取出顺序依次为“右、左、右、右、右、左、左”

样例2

输入

4,5,6,7,0,1,2
6,0,5,1,2,4,7

输出

NO

说明

无法取出对应序列的篮球

样例3

输入

1,2,3,4
1,2,3,5

输出

NO

说明

不存在编号为 $5$ 的篮球，所以无法取出对应编号的数据