题解

题面描述

给定 $T$ 组测试数据，每组测试数据包含一个字符串数组。定义字符串数组为单调不降当且仅当对于所有相邻元素 $s[i]$ 和 $s[i+1]$，都有 $s[i]\le s[i+1]$，其中比较规则为：

1. 首先按照字符串的长度比较，长度更长的字符串更大，如 $banana > apple$
2. 在长度相等的情况下，按字符串的字典序比较，字典序较大的字符串更大，如 $cherry > banana$

思路

1. 初始化：令当前长度计数器 $\text{cur} = 1$，最大长度 $\text{ans} = 1$。
2. 遍历：从 $i = 1$ 到 $n-1$（按 0 下标）：
   • 比较 $s[i-1]$ 和 $s[i]$：
     • 若 $s[i-1] \le s[i]$，则 $\text{cur}++$；
     • 否则，更新 $\text{ans} = \max(\text{ans}, \text{cur})$，并重置 $\text{cur} = 1$。
3. 结束后：再更新一次 $\text{ans} = \max(\text{ans}, \text{cur})$。
4. 输出 $\text{ans}$。

C++

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

// 判断字符串 a 是否小于等于 b
bool le(const string& a, const string& b) {
    if (a.length() != b.length())
        return a.length() < b.length();   // 长度更小则更小
    return a <= b;                         // 长度相等按字典序
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<string> s(n);
        for (int i = 0; i < n; i++) {
            cin >> s[i];
        }

        int cur = 1, ans = 1;
        for (int i = 1; i < n; i++) {
            if (le(s[i-1], s[i])) {
                cur++;                    // 连续子数组长度加一
            } else {
                ans = max(ans, cur);     // 更新最大值
                cur = 1;                 // 重置计数器
            }
        }
        ans = max(ans, cur);            // 末尾更新
        cout << ans << '\n';
    }

    return 0;
}

Python

import sys

# 判断字符串 a 是否小于等于 b
def le(a: str, b: str) -> bool:
    if len(a) != len(b):
        return len(a) < len(b)    # 长度更小则更小
    return a <= b                  # 长度相等按字典序

T = int(sys.stdin.readline())
for _ in range(T):
    n = int(sys.stdin.readline())
    s = sys.stdin.readline().split()

    cur = ans = 1
    for i in range(1, n):
        if le(s[i-1], s[i]):
            cur += 1                # 连续子数组长度加一
        else:
            ans = max(ans, cur)    # 更新最大值
            cur = 1                # 重置计数器
    ans = max(ans, cur)            # 末尾更新
    print(ans)

Java

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

public class Main {
    // 判断字符串 a 是否小于等于 b
    static boolean le(String a, String b) {
        if (a.length() != b.length()) {
            return a.length() < b.length();  // 长度更小则更小
        }
        return a.compareTo(b) <= 0;           // 长度相等按字典序
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            int n = Integer.parseInt(br.readLine());
            String[] s = br.readLine().split(" ");

            int cur = 1, ans = 1;
            for (int i = 1; i < n; i++) {
                if (le(s[i-1], s[i])) {
                    cur++;                   // 连续子数组长度加一
                } else {
                    ans = Math.max(ans, cur); // 更新最大值
                    cur = 1;                 // 重置计数器
                }
            }
            ans = Math.max(ans, cur);     // 末尾更新
            System.out.println(ans);
        }
    }
}

题目内容

多多君正在研究字符串数组的单调性。他定义一个字符串数组为单调不降当且仅当对于所有相邻元素 $s[i]$ 和 $s[i+1]$ ，都有 $s[i]≤s[i+1]$ ，其中 $≤$ 表示：

1.首先按照字符串的长度比较，长度更长的字符串更大，如 $banana > apple$

2.在长度相等的情况下，按字符串的字典序比较，字典序较大的字符串更大，如 $cherry>banana$

给定若干组测试数据，每组数据包含一个字符串数组。你需要计算该数组中最长的单调不降连续子数组的长度。

输入描述

第一行为一个整数 $T(1≤T≤1000)$ ，表示测试用例的数量。

接下来的 $2T$ 行，每两行表示一组测试用例：

第一行为当前测试用例输入的字符串数组的长度 $n (1≤n≤1000)$

第二行为 $n$ 个由空格分隔的字符串，对应字符串数组中的每个元素；

其中每个字符串仅包含小写字母，长度不超过 20

输出描述

输出包含 $T$ 行

每一行为对应测试用例中，最长的单调不降连续子数组的长度

补充说明

$20$% 数据满足 $n≤100$

$50$%数据满足 $n≤500$

$100$% 数据满足 $n≤1000$

长度为1的字符串数组也可以视为单调不降

样例1

输入

2
3
apple banana cherry
4
dog cat bird elephant

输出

3
3

说明

第一组数据中，$apple<banana<cherry$，所以结果为 $3$

第二组数据中，$dog>cat,cat<bird，bird<elephant$ , 所以结果为 $3$

样例2

输入

2
4
aaaa bbb cc d
5
test test test test test

输出

1
5

说明

第一组数据中，$aaaa>bbb>cc>d$ ，考虑到长度为 $1$ 的字符串数组也可以视为单调不降，所以结果为 $1$

第二组数据中，所有 $test$ 首先长度相同、其次字典序相等，因此满足单调不递减的定义，所以结果为 $5$