13 solutions

  • 2
    @ 2022-4-2 10:41:33

    这题 真的很好,我被 题目 的意思 给卡住了。读了半天 都没太理解什么意思。看了下 其他人的 题解,发现 原来 C 站 是要 先进后出好像。那就简单多了,无非就是 在 A 轨道 选择一下数,看下 有没有,如果没有对应上的,那就 去 看看 C 站 里 有没有,如果 俩者 都不行,那算了,那就把这个数字 放到 C 站立就行了。

    依次 选择数字下去,如果 能够 凑出 给定的顺序 就是 YES,如果凑不出,那就是 NO。

    #define _CRT_SECURE_NO_WARNINGS
    
    #include <iostream>
    #include <stack>
    
    using namespace std;
    
    const int N = 1e5 + 7;
    
    int B[N];// 我们给的顺序 也是 最后 B 轨道 应该的顺序
    
    int main(void) {
    	// 从 A 方向 来的火车 进入 C 车站之前 都不是 连接着的。
    	// 这些火车 可以 自行 移动到 B 处 的 铁轨
    	// C 车站 可以 随意 停放 多节车厢
    	// 进入到了 C 车站后,就不能 再回到 A 方向的铁轨
    	// 进入了 B 方向 铁轨 也不能再回到 车站 C
    	// 从 C 车站到 B 的,必须 按照 先进后出的 顺序 !!!
    
    
    	//最终目的 是 使其 a1 a2 a3 的顺序 从 B 方向驶出。这个 顺序 是我们指定的
    	int n;
    	cin >> n;
    
    	for (int i = 0; i < n; ++i) {
    		cin >> B[i];
    	}
    	int sub = 0;// 
    	stack<int> s;
    	// 先从 A 轨道 选 车厢
    	for (int i = 1; i <= n; ++i) {
    		while (!s.empty() && s.top() == B[sub]) {// 可能 C 车站里 有车厢 可以选
    			sub++;
    			s.pop();
    		}
    		if (i == B[sub]) {// 则 满足 条件,
    			sub++;// 证明 从 A 直接 到 B 就行,然后 下一个 位置的 数字需要 进行判断
    		}
    		else {
    			s.push(i);// 不能选的话,那就放到 C 车站里
    		}
    	}
    
    	bool flag = true;// 默认是可以 实现目的的
    
    	while (!s.empty()) {
    		if (s.top() != B[sub]) {
    			flag = false;
    			break;
    		}
    		else {
    			s.pop();
    			sub++;
    		}
    	}
    
    	
    	if (flag) {
    		cout << "YES" << endl;
    	}
    	else {
    		cout << "NO" << endl;
    	}
    
    
    	return 0;
    }
    

    代码 可能 跟 第一位 大佬的题解差不多,但是 根据思路来说,确实 也不会写的 相差多少。反而 是接近一样才对。

    Information

    ID
    291
    Time
    1000ms
    Memory
    128MiB
    Difficulty
    6
    Tags
    # Submissions
    139
    Accepted
    44
    Uploaded By