得物笔试得物秋招得物笔试题 0920

笔试时间：2025年9月20日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：洗盘子

题目描述：小A在餐馆打工，他的主要工作就是洗盘子。某一天餐厅有 n 个盘子需要清洗，从上到下编号 1-n，小A只会每次拿最上面连续的若干个编号连续的盘子 i-j，然后按照 i-j 的顺序来洗它们。

现在，给出一个人洗这个盘子的顺序，请你判断一下是否可能是小A洗盘子的顺序。

输入描述

第一行一个整数 t 表示数据组数。

对于每组数据：

第一行一个整数 n
第二行 n 个整数 a₁-aₙ，数字间两两有空格隔开，表示某个人洗盘子的顺序

数据范围：1≤t≤10, 1≤n≤1000

输出描述

输出 t 行，每行一个单词，如果可能是小A洗的，则输出 yes，否则输出 no。

样例输入

2

5

1 2 5 4 3

5

1 2 5 3 4

样例输出

yes

no

样例说明： 第一组样例：先拿出盘子1，再拿出盘子2，再拿出盘子3~5。第二组样例：不可能是小A洗的。

参考题解

解题思路：

将输入序列分割成多个连续递减的子序列（段）。分割规则是当当前元素大于前一个元素时，结束当前段并开始新段。
检查每个段内的数字是否构成连续的数值序列。对于长度大于1的段，要求相邻元素必须严格递减且差值为1。
确保段与段之间满足递增关系，即后一段的最小值必须大于前一段的最大值。

C++：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool is_valid_sequence(vector<int>& arr) {
    int n = arr.size();
    if (n == 0) return true;
    
    vector<vector<int>> segments;
    vector<int> current_segment;
    current_segment.push_back(arr[0]);
    
    for (int i = 1; i < n; i++) {
        if (arr[i] < arr[i-1]) {
            current_segment.push_back(arr[i]);
        } else {
            segments.push_back(current_segment);
            current_segment.clear();
            current_segment.push_back(arr[i]);
        }
    }
    segments.push_back(current_segment);
    
    // Check each segment
    for (auto& segment : segments) {
        if (segment.size() > 1) {
            for (int j = 1; j < segment.size(); j++) {
                if (segment[j-1] - segment[j] != 1) {
                    return false;
                }
            }
        }
    }
    
    // Check segments order
    for (int i = 1; i < segments.size(); i++) {
        int prev_max = *max_element(segments[i-1].begin(), segments[i-1].end());
        int curr_min = *min_element(segments[i].begin(), segments[i].end());
        if (curr_min <= prev_max) {
            return false;
        }
    }
    
    return true;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> arr(n);
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        if (is_valid_sequence(arr)) {
            cout << "yes" << endl;
        } else {
            cout << "no" << endl;
        }
    }
    return 0;
}

Java：

import java.util.*;

public class Main {
    public static boolean isValidSequence(int[] arr) {
        int n = arr.length;
        if (n == 0) return true;
        
        List<List<Integer>> segments = new ArrayList<>();
        List<Integer> currentSegment = new ArrayList<>();
        currentSegment.add(arr[0]);
        
        for (int i = 1; i < n; i++) {
            if (arr[i] < arr[i-1]) {
                currentSegment.add(arr[i]);
            } else {
                segments.add(new ArrayList<>(currentSegment));
                currentSegment.clear();
                currentSegment.add(arr[i]);
            }
        }
        segments.add(currentSegment);
        
        // Check each segment
        for (List<Integer> segment : segments) {
            if (segment.size() > 1) {
                for (int j = 1; j < segment.size(); j++) {
                    if (segment.get(j-1) - segment.get(j) != 1) {
                        return false;
                    }
                }
            }
        }
        
        // Check segments order
        for (int i = 1; i < segments.size(); i++) {
            int prevMax = Collections.max(segments.get(i-1));
            int currMin = Collections.min(segments.get(i));
            if (currMin <= prevMax) {
                return false;
            }
        }
        
        return true;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = sc.nextInt();
            }
            if (isValidSequence(arr)) {
                System.out.println("yes");
            } else {
                System.out.println("no");
            }
        }
        sc.close();
    }
}

Python：

def is_valid_sequence(arr):
    n = len(arr)
    if n == 0:
        return True
    
    segments = []
    current_segment = [arr[0]]
    
    for i in range(1, n):
        if arr[i] < arr[i - 1]:
            current_segment.append(arr[i])
        else:
            segments.append(current_segment)
            current_segment = [arr[i]]
    segments.append(current_segment)
    
    for segment in segments:
        if len(segment) > 1:
            for j in range(1, len(segment)):
                if segment[j - 1] - segment[j] != 1:
                    return False
    
    for i in range(1, len(segments)):
        prev_max = max(segments[i - 1])
        curr_min = min(segments[i])
        if curr_min <= prev_max:
            return False
    
    return True

t = int(input().strip())
for _ in range(t):
    n = int(input().strip())
    arr = list(map(int, input().split()))
    
    if is_valid_sequence(arr):
        print("yes")
    else:
        print("no")