题解思路

这是一道巧妙的双端队列模拟问题，需要理解火车站的运作机制和约束条件。

1. 问题建模分析

关键理解：

• 火车按编号1,2,...,n的顺序进站
• 车站可以看作一个双端队列，新火车从左端进入
• 出站口1（原进站口）对应从左端出站
• 出站口2（直行轨道）对应从右端出站
• 只有位于队列两端的火车才能出站

约束条件：

• 火车必须严格按1,2,...,n的顺序进站
• 每次出站的火车必须位于队列的左端或右端
• 需要验证给定出站序列是否可行

2. 双端队列模拟算法

核心思想：

• 使用双端队列维护当前站内的火车
• 对于出站序列中的每辆火车，尝试让其到达队列两端
• 如果无法到达任一端，则序列不可行
• 优先选择从左端（出站口1）出站，以最大化答案

算法流程：

1. 初始化空的双端队列和next_in=1（下一个进站的火车编号）

2. 对于出站序列中的每个火车need：

   • 循环进站操作：如果need不在队列两端且还有火车未进站，则让下一辆火车进站
   • 尝试出站：如果need在左端，从左端出站并计数；如果need在右端，从右端出站
   • 如果need无法到达两端，返回-1

3. 贪心策略证明

为什么优先选择左端出站是最优的？

因为我们要最大化从出站口1出站的火车数量，所以当火车既可以从左端出站也可以从右端出站时，应该优先选择左端。这样的贪心选择不会影响后续的可行性，因为：

• 从左端出站的火车不会阻挡其他火车的出站路径
• 从右端出站的火车可能会阻挡后续火车从右端出站

4. 复杂度分析

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

  • 每辆火车最多进站一次，出站一次
  • 双端队列的操作均为$O(1)$

• 空间复杂度：$O(n)$（双端队列存储）

Java题解代码

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

public class Main {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine().trim());
        String[] tokens = br.readLine().trim().split("\\s+");
        int[] sequence = new int[n];
        
        for (int i = 0; i < n; i++) {
            sequence[i] = Integer.parseInt(tokens[i]);
        }
        
        int result = maxTrainsFromExit1(n, sequence);
        System.out.println(result);
    }
    
    private static int maxTrainsFromExit1(int n, int[] sequence) {
        Deque<Integer> station = new LinkedList<>(); // 双端队列模拟车站
        int nextTrainToEnter = 1; // 下一个要进站的火车编号
        int exit1Count = 0; // 从出站口1出站的火车数量
        
        for (int targetTrain : sequence) {
            // 让目标火车到达队列的某一端
            while ((station.isEmpty() || 
                   (station.peekFirst() != targetTrain && station.peekLast() != targetTrain)) 
                   && nextTrainToEnter <= n) {
                
                // 新火车从左端进站
                station.addFirst(nextTrainToEnter);
                nextTrainToEnter++;
            }
            
            // 尝试让目标火车出站
            if (!station.isEmpty() && station.peekFirst() == targetTrain) {
                // 从左端（出站口1）出站
                station.removeFirst();
                exit1Count++;
            } else if (!station.isEmpty() && station.peekLast() == targetTrain) {
                // 从右端（出站口2）出站  
                station.removeLast();
            } else {
                // 目标火车无法到达任一端，序列不可行
                return -1;
            }
        }
        
        return exit1Count;
    }
}

C++题解代码

#include <iostream>
#include <deque>
#include <vector>
#include <ios>

using namespace std;

class TrainStationSolver {
public:
    int maxTrainsFromExit1(int n, const vector<int>& sequence) {
        deque<int> station; // 双端队列模拟车站
        int nextTrainToEnter = 1; // 下一个进站的火车编号
        int exit1Count = 0; // 从出站口1出站的计数
        
        for (int targetTrain : sequence) {
            // 循环进站直到目标火车到达队列两端之一
            while ((station.empty() || 
                   (station.front() != targetTrain && station.back() != targetTrain)) 
                   && nextTrainToEnter <= n) {
                
                station.push_front(nextTrainToEnter); // 新火车从左端进站
                nextTrainToEnter++;
            }
            
            // 尝试出站操作
            if (!station.empty() && station.front() == targetTrain) {
                // 从左端（出站口1）出站，优先选择
                station.pop_front();
                exit1Count++;
            } else if (!station.empty() && station.back() == targetTrain) {
                // 从右端（出站口2）出站
                station.pop_back();
            } else {
                // 无法让目标火车到达两端，序列不合法
                return -1;
            }
        }
        
        return exit1Count;
    }
    
    void solve() {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
        
        int n;
        cin >> n;
        
        vector<int> sequence(n);
        for (int i = 0; i < n; i++) {
            cin >> sequence[i];
        }
        
        int result = maxTrainsFromExit1(n, sequence);
        cout << result << "\n";
    }
};

int main() {
    TrainStationSolver solver;
    solver.solve();
    return 0;
}