洛谷刷题记——U96235 小明看报纸（newspaper）

最近过了一遍过去做的难题，发现这道题题面和数据有些许更新，决定再把这道题做一遍。

题目描述

见https://www.luogu.com.cn/problem/U96235。

知识链接

稳定排序

如何改变字符串大小写？

在这篇题解中我们用到了字符串改变大小写。那么，怎么实现呢？

C++中并没有内置大小写转换工具，我们可以使用<algorithm>中的std::transform()工具：

std::transform(str1.begin(), str1.end(), str2.begin(), ::toupper);

这段代码的作用是将字符串str1的所有小写字母转换为大写字母，并将转换后的字符串覆盖到str2中（注意，str1不会被改变）。如要改变原字符串，将上述代码中的“str2”改为“str1”即可。

相应地，如果要全部改为小写，将上述代码中的“::toupper”改为“::tolower”即可。

这还不是transform的全部用法，欲了解详情请参考http://c.biancheng.net/view/623.html。

结构体排序

请参考https://blog.csdn.net/oliver233/article/details/70215215。

解题思路

根据题目，可以得出我们需要做以下两件事情（不包含输入输出）：

一、将字符串中所有的元音字母转换为下划线“_”。
二、求出字符串中含有元音字母的个数，从小到大稳定排序（我做的时候还不需要稳定排序，不稳定排序也行）。

我们可以采取边输入边处理的方式，一次读入一行。由于题中没有固定输入几行，我们可以使用getline()搭配while循环的方式：

while (getline(cin, str))
{
    pass; // 在此输入代码内容
}

为了让字符串随元音字母个数排序，我们可以采用结构体的方式储存：

struct sentence
{
    int cntVowel; // 元音字母个数
    string s; // 字符串
};

而判断是否是元音字母，我们可以采用switch：

switch (sentences[i].s[j]) // 判断当前字母
{
    case 'A': case 'E': case 'I': case 'O': case 'U': // 如果是元音字母
        sentences[i].s[j] = '_'; // 替换为下划线
        ++(sentences[i].cntVowel); // 当前句子元音字母个数＋1

        break; // 退出

    default: // 如果不是
        break; // 直接退出
}

排序没啥好说的，直接放代码：

stable_sort(sentences.begin(), sentences.begin() + i, cmp); // 稳定排序

代码展示

拒绝抄袭，共创和谐社会[机智]

#include <algorithm> // std::transform
#include <array> // std::array
#include <cctype> // ::toupper
#include <iostream> // std::cin, std::cout, std::endl
#include <string> // std::string

using namespace std;

// 结构体
struct sentence
{
    int cntVowel;
    string s;
};

// 结构体数组，这里莫名其妙用了指针（我也不知道为啥）
// 另外，注意一下这个数组大小（我做的时候还是5000），题面中说是70%的数据大小，但实际上可以100%全AC
array<sentence*, 210010> sentences;

// 自定义比较函数
bool cmp(sentence*, sentence*);

int main(void)
{
    int cntTotal = 0, cntVowel = 0, i = 0;
    sentence* tmp = new sentence;

    for (array<sentence*, 210010>::iterator iter = sentences.begin(); iter != sentences.end(); iter++) // 初始化数组，又莫名其妙用了迭代器
    {
        *iter = new sentence;
        (*iter)->cntVowel = 0;
    }

    while (getline(cin, sentences.at(i)->s)) // 主循环，输入＋处理
    {
        if (sentences.at(i)->s.size() != 0) // 排除空行
        {
            tmp->s = sentences.at(i)->s;
            transform(tmp->s.begin(), tmp->s.end(), tmp->s.begin(), ::toupper); // 将所有的小写字母转为大写字母，这样就不用再比较小写的元音字母了

            for (int j = 0; j < sentences.at(i)->s.size(); j++) // 遍历所有的字母
            {
                switch (tmp->s.at(j)) // 比较
                {
                case 'A': case 'E': case 'I': case 'O': case 'U':
                    sentences.at(i)->s.at(j) = '_';
                    ++(sentences.at(i)->cntVowel);

                    break;

                default:
                    break;
                }
            }

            ++i; // 字符串总个数＋1
        }
    }

    stable_sort(sentences.begin(), sentences.begin() + i, cmp); // 稳定排序

    for (int j = 0; j < i; j++) // 输出
    {
        cout << sentences.at(j)->s << " (" << sentences.at(j)->cntVowel << '/' << sentences.at(j)->s.size() << ')' << endl; // 按照格式，注意后面括号的内容哦
    }

    for (array<sentence*, 210010>::iterator iter = sentences.begin(); iter != sentences.end(); iter++) // 删除指针，又莫名其妙用了迭代器
    {
        delete *iter;
    }

    return 0;
}

// 自定义比较函数实现
bool cmp(sentence* x, sentence* y)
{
    return (x->cntVowel < y->cntVowel);
}

写在最后

这道题还是有一定难度的，最近题面也有更新，不过总算说又搞定一道题了\(^o^)/YES!