pta c++求最大字符串

在 C++ 中，如果你想要找到两个字符串中较大的一个，可以编写一个函数来比较它们的长度，因为如果字符串一样长则字典序决定了顺序。下面是一个简单的示例：

#include <string>

std::string maxString(std::string str1, std::string str2) {
    if (str1.length() > str2.length()) {
        return str1;
    } else if (str1.length() < str2.length()) {
        return str2;
    } else { // 如果长度相等，则直接返回
        return str1; // 这里假设第一个字符串就是较大的（你可以根据需要更改这个判断条件）
    }
}

int main() {
    std::string s1 = "apple";
    std::string s2 = "banana";
    std::string max = maxString(s1, s2);
    std::cout << "The maximum string is: " << max << std::endl;
    return 0;
}

在这个例子中，`maxString` 函数接受两个 `std::string` 类型的参数，通过比较它们的长度，确定并返回较长的那个。

相关问题

PTA字符串最大和最小字符串

题目描述：

给定一个长度为$n$的字符串，求出字典序最小和最大的子串。

输入格式：

第一行一个数$n$ $(1\leq n\leq10^5)$。

第二行为长度为$n$的字符串。

输出格式：

输出两行，分别为最小和最大字典序的子串。

输入样例：

7
abacaba

输出样例：

a
caba

算法1：

(暴力枚举) $O(n^2)$

暴力枚举所有子串，根据字典序找出最大和最小的子串。

时间复杂度分析：该算法暴力枚举所有子串，时间复杂度为$O(n^2)$，无法通过本题。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
char s[N];
int main()
{
    int n;
    scanf("%d%s",&n,s+1);
    string ans1="~",ans2="";
    for(int i=1;i<=n;i++)//枚举左端点
        for(int j=i;j<=n;j++)//枚举右端点
        {
            string t=s+to_string(i);
            t=t.substr(0,j-i+1);
            ans1=min(ans1,t);
            ans2=max(ans2,t);
        }
    printf("%s\n%s\n",ans1.c_str(),ans2.c_str());
    return 0;
}

算法2：

(前缀和+二分答案) $O(n\log n)$

枚举子串长度，然后通过计算前缀和的差值得出所有长度为$k$的子串，然后对这些子串进行字典序的比较，即可得到最小和最大字典序的子串。

具体地，如果要求一个长度为$k$的最小字典序的子串，可以先计算出所有长度为$k$的子串的前缀和，然后对这些前缀和进行排序，最小字典序的子串就是前缀和相邻两个元素之间的差值最小的子串。

同样，如果要求一个长度为$k$的最大字典序的子串，可以先计算出所有长度为$k$的子串的前缀和，然后对这些前缀和进行排序，最大字典序的子串就是前缀和相邻两个元素之间的差值最大的子串。

时间复杂度分析：该算法枚举子串长度，时间复杂度为$O(n)$，计算前缀和的时间复杂度为$O(n)$，排序的时间复杂度为$O(n\log n)$，因此该算法的总时间复杂度为$O(n\log n)$。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n;
char s[N];
bool check(int k,int x)
{
    vector<int> a(n+1),f(n+1);
    for(int i=1;i<=n;i++) a[i]=a[i-1]+(s[i]-'a'+1>x?1:-1);//计算前缀和
    int mi=0;
    for(int i=k;i<=n;i++)//枚举右端点
    {
        mi=min(mi,f[i-k]);//维护长度为k的子串最小的前缀和
        if(a[i]-mi>0) return true;
        f[i]=min(f[i-1],a[i-k]);//更新长度为k的子串最小的前缀和
    }
    return false;
}
int main()
{
    scanf("%d%s",&n,s+1);
    int l=1,r=26*n,ans1=-1,ans2=-1;
    while(l<=r)//二分子串长度
    {
        int mid=l+r>>1;
        if(check(mid,-1)) ans2=mid,l=mid+1;//更新最小字典序子串
        else r=mid-1;
    }
    l=1,r=26*n;
    while(l<=r)//二分子串长度
    {
        int mid=l+r>>1;
        if(check(mid,1)) ans1=mid,r=mid-1;//更新最大字典序子串
        else l=mid+1;
    }
    string t1,t2;
    for(int i=1;i<=n;i++)//枚举左端点
    {
        int j=i+ans1-1;
        if(j>n) break;
        string t=s+to_string(i);
        t=t.substr(0,ans1);
        t1=max(t1,t);
    }
    for(int i=1;i<=n;i++)//枚举左端点
    {
        int j=i+ans2-1;
        if(j>n) break;
        string t=s+to_string(i);
        t=t.substr(0,ans2);
        t2=min(t2,t);
    }
    printf("%s\n%s",t2.c_str(),t1.c_str());
    return 0;
}

pta6-2 字符串的删除

题目描述：

给定一个字符串S和一个字符T，从S中删除所有的T字符，输出删除后的字符串。字符串中可能包含空格。

输入格式：

第一行输入一个字符串S。

第二行输入一个字符T。

输出格式：

输出删除后的字符串。

数据范围：

1≤∣S∣≤10000

输入样例：

They are students
aeiou

输出样例：

Thy r stdnts

算法1：

C++ 代码