rails

链接

这道题,问你火车进站再出站的车厢可能排列情况(全英文也太阴了吧)

我们默认左边是车头,不妨假设只有5节车厢,为1 2 3 4 5进站

假设5在最前,我们发现必须把车一起开进站,那么只能是5 4 3 2 1了

假设4在最前,我们发现前四节车厢必须一起开进站,只能是4 3 2 1,而第五节车厢可以放入任意位置

发现规律了,我们的车厢后面比自己小的车厢必须严格单调递减

比如 4 5 3 2 1是递减的,因为5比4大,不算进去

3 4 5 2 1也是递减的

那么,方法有了,怎么用代码实现呢,我们不妨设一个current=当前车厢-1,接着将current右移,当current遇到小于等于自己的数字时,current进行赋值,一旦遇到比自己大却比一开始的车厢数字小时,直接返回No

没遇到返回No的情况就返回Yes

代码实现

#include<bits/stdc++.h>
using namespace std;
string func(vector<int>ans){
    for (int i = 0;i < ans.size()-1;i++) {
     int count = ans[i] - 1;
     for (int j = i+1;j < ans.size();j++) {
         if (ans[j] < ans[i] && ans[j] <= count) {
             count = ans[j];
         }
         else if (ans[j] < ans[i] && ans[j] > count) {
             return "No";
         }
     }
 }
 return "Yes";
}
int main(){
    int n;
    while(cin >> n && n != 0){
        while(true){
            vector<int> ans;
            int first;
            cin >> first;
            if(first == 0){
                cout << endl; 
                break;
            }
            ans.push_back(first);
            for(int i = 1; i < n; i++){
                int num;
                cin >> num;
                ans.push_back(num);
            }
            cout << func(ans) << endl;
        }
    }
    return 0;
}

时间复杂度O(n²) 空间复杂度:O(n)