c++ - 对自定义 2D 矢量进行排序会引发运行时错误。我该如何解决？

问题描述

我正在尝试根据特定字符的字符数与其余字符之间的差异对 2D 向量进行排序。它适用于大多数测试用例，但对于这个特定的测试用例似乎失败了。经过一些调试，我发现当 ch='d' 和 ch='e' 用于以下测试用例时，它会出现运行时错误。我无法弄清楚这里到底发生了什么。

链接到问题：-

https://codeforces.com/contest/1551/problem/C

我的逻辑：- 对于每个字符 {az} 说 ch，这可能是删除某些字符串后出现次数最多的决定字符，我试图消除 ch 的最大频率差异减去其他字符的字符串。

typedef long long int ll;
void solve()
{
    ll n;
    string s;
    cin>>n;
    vector<vector<ll>>v(n,vector<ll>(5,0));
    unordered_map<char, ll>m;
    vector<string>str;
    unordered_map<char, ll>old;
    for(ll i=0;i<n;i++)
    {   
        cin>>s;
        str.push_back(s);
    }
    for(ll i=0;i<n;i++)
    {   
        for(ll j=0;j<str[i].length();j++)
        {
            v[i][str[i][j]-97]++;
            m[str[i][j]]++;
        }
    }
    old=m;
    ll ans=0;
    for(char ch='a';ch<='e';ch++)
    {  
        m=old;
        ll sum=m['a']+m['b']+m['c']+m['d']+m['e'];
        if(sum-m[ch]<m[ch])
        {
            ans=max(ans,n);
        }
        sort(v.begin(),v.end(),[ch](const vector<ll>&a,const vector<ll>&b)
        {   
            return (a[ch-97]-(a[0]+a[1]+a[2]+a[3]+a[4]))<=(b[ch-97]-(b[0]+b[1]+b[2]+b[3]+b[4]));
        });
     
        for(ll i=0;i<n;i++)
        {   
            for(ll j=0;j<5;j++)
            {   
                m[j+97]=m[j+97]-v[i][j];
            }
            ll sumrest=m['a']+m['b']+m['c']+m['d']+m['e'];
            if(m[ch]>sumrest-m[ch])
            {
                ans=max(ans,n-i-1);
            }  
        }
    }
    cout<<ans<<"\n";
}

测试用例：-

1
43
a
d
bbc
a
dda
c
e
bb
cbd
c
dc
e
caab
d
c
e
e
bd
d
a
a
b
a
c
d
c
d
ba
e
c
ecdb
bdbd
d
e
cb
ac
ccd
cb
cda
da
bb
d
c

标签： c++c++11debuggingruntime-errorc++17

解决方案

您关于排序的问题的答案已经在评论中给出。您提供的 Lambda 不满足严格弱排序的要求。因此，如果您想继续使用您的方法，那么您需要更改 Lambda。

不幸的是，我不得不说你的设计是错误的，而且你开始编写代码太早了。我将向您展示如何解决此类问题的更好策略。

与经典的软件开发方法一样，我们应该从需求获取/需求分析开始。其结果将用于设计/详细设计。由于任务简单，我们可以跳过详细设计。

在大多数情况下，Codeforces（和其他此类网站）以文本形式对问题的描述总是有些复杂，因此，需求分析是强制性的。

斯蒂芬·奎恩想写一个故事。他是一个非常不寻常的作家，他只使用字母“a”、“b”、“c”、“d”和“e”！

消除噪声，要求是：

使用 'a','b','c','d','e' 作为数据元素。数据元素是连续的

为了撰写一个故事，斯蒂芬写出了由拉丁字母的前 5 个小写字母组成的 n 个单词。他想选择最大数量的单词来制作一个有趣的故事。

消除噪声，要求是：

将有给定数量的单词（n）
我们需要在特定条件下找到这些单词的最大数量

让一个故事是一个不一定不同的单词序列。如果有一个字母在故事的所有单词中出现的次数比所有其他字母加起来的次数多，那么这个故事就被称为有趣。

消除噪声，要求是：

在单词列表中可能有重复
选择单词的条件，使得一个选定字符（'a'，'b'，'c'，'d'，'e'）的总和大于所有其他字符的总和
将对单词列表中的 1 个或多个单词进行求和

例如，由“bac”、“aaada”、“e”三个词组成的故事很有趣（字母“a”出现 5 次，所有其他字母总共出现 4 次）。但是由“aba”、“abcde”这两个词组成的故事不是（没有这样的字母，它出现的次数比所有其他字母都多）。给定一个由字母“a”、“b”、“c”、“d”和“e”组成的 n 个单词的序列。你的任务是选择他们的最大数量来制作一个有趣的故事。如果无法制作非空故事，则输出 0。

消除噪声，要求是：

输出满足条件的单词数（或 0，如果没有）

输入。第一行包含一个整数 t (1≤t≤5000) — 测试用例的数量。然后是 t 个测试用例。每个测试用例的第一行包含一个整数 n (1≤n≤2⋅10 5) — 序列中单词的数量。然后是 n 行，每行包含一个单词——一个由拉丁字母的小写字母组成的非空字符串。序列中的单词可能不明确（即允许重复）。单词中只能出现字母“a”、“b”、“c”、“d”和“e”。

消除噪声，要求是：

第一个输入是测试用例的数量
测试用例范围1-5000
然后所有测试用例都遵循
每个测试用例以单词数开头
单词不是空的，可能是重复的，并且由上述元素组成

保证所有测试用例的n之和不超过2⋅10 5；所有测试用例中所有单词的长度之和不超过 4⋅10 5。

消除噪声，要求是：

总共最多有 2 10 5 个单词
所有单词加在一起的长度只有 4 10 5

输出：对于每个测试用例，输出构成有趣故事的最大单词数。如果没有办法制作一个非空有趣的故事，则打印 0。

消除噪声，要求是：

在单独的行中显示每个测试用例的结果

所以，这都是要求：

使用 'a','b','c','d','e' 作为数据元素。数据元素是连续的

要求摘要

将有给定数量的单词（n）
我们需要在特定条件下找到这些单词的最大数量
在单词列表中可能有重复
选择单词的条件，使得一个选定字符（'a'，'b'，'c'，'d'，'e'）的总和大于所有其他字符的总和
将对单词列表中的 1 个或多个单词进行求和
输出满足条件的单词数（或 0，如果没有）
第一个输入是测试用例的数量
测试用例范围1-5000
然后所有测试用例都遵循
每个测试用例以单词数开头
单词不是空的，可能是重复的，并且由上述元素组成
总字数最多为 2 10 5
所有单词加在一起的长度只有 4 10 5
在单独的行中显示每个测试用例的结果
使用 'a','b','c','d','e' 作为数据元素。数据元素是连续的

现在，我们可以从设计开始。

(1), (10) (12): 字数将在运行时给出。最大数量已知 --> 我们将使用 a std::vectorofstd::string来存储单词

(3)：不相关

(12), (13)。数据类型unsigned int足以存储所有值

(5)：我们需要对列表中的所有单词进行操作，直到找到一个结果。

(4)：这是最重要的一个，描述了算法。让我们从一个字母开始。我们稍后将简单地扩展所有其他字母的解决方案。

所以，我们需要做的是计算所有的“a”字母。显然还有所有其他字母。为了获得好的结果，Count 'a' 必须大于 Count 'others' 所以：

Count ‘a’ > Count ‘others’      or     Count ‘a’ - Count ‘others’ >0

这意味着，如果我们找到一个“a”，我们可以增加一个计数器，然后减少所有其他字母的计数器。

(5) 将对列表中的每个单词进行计数。

(6) 我们需要选择满足条件：Counter > 0 的字数。因此，为了实现这一点，我们需要将计数器从大到小排序并将它们相加。一旦总和小于 0，则该词不属于结果集。

(2) 我们对所有字母执行 (6) (14)，并找出该字母的最大结果数。这将输出到std::cout

(7)、(8)。在开始时将测试用例的数量读入unsigned integer.

(9) 评估所有测试用例。

(15) 一个词有5个元素。它们是连续的。我们可以使用简单的循环对它们进行操作。

(8)、(11)、(12)、(13)、(15)。所有值均已定义。输入范围明确。最大数据类型需要是unsigned integer. 字母将存储为字符。无需输入验证。在必要的reding之前不需要初始化变量std::cin，因为所有输入值都保证是正确的。

这是一种可能的解决方案：

#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <algorithm>

constexpr std::array<char, 5> Letters{{'a','b','c','d','e'}};

int main() {
    // Get number of test cases
    unsigned int numberOfTestCases; std::cin >> numberOfTestCases;
    
    // Work on all test cases
    while (numberOfTestCases--  > 0) {
        
        // Now, read the number of words that will be used in this test cases
        unsigned int numberOfWords; std::cin >> numberOfWords;
        
        // Here we will store all words for thsi test case. Number is known
        std::vector<std::string> words(numberOfWords);
        
        // Read all words from std::cin for this test case
        for (std::string& word : words) std::cin >> word;
        
        // Here we will store the result overall for this test case
        size_t resultForThisTestCase{};
        
        // Now make the evaluation for all Letters
        for (const char letter : Letters) {
        
            // We will count all occurences for this letter 
            // (subtracted by other letters) for all words
            std::vector<int> letterCounter(numberOfWords);
            
            // Check all words of this test case
            for (size_t wordIndex{}; wordIndex < numberOfWords; ++wordIndex) 
            {
                // Evaluate all letters of this word and count up or down
                for (const char c : words[wordIndex])
                    if (letter == c)
                        ++letterCounter[wordIndex];
                    else
                        --letterCounter[wordIndex];
            }
            
            // Sort counters for this one letter from large to small,
            // because only the big numbers are relevant
            std::sort(letterCounter.begin(), letterCounter.end(), std::greater<int>());
            
            // Now, for all counters of the words and as long as counts are positive (meaning
            // the count of this letter is larger than for all other letters)
            int sumOfCounters{};
            
            for (size_t counterIndex{}; counterIndex < numberOfWords; ++counterIndex) {
                
                // Sum up counters
                sumOfCounters += letterCounter[counterIndex];
                
                // End condition. If count of this letter is smaller than the count of
                // all other letters, then this word does not belong to the result
                if (sumOfCounters <= 0) break;
                
                // We are still looping, so this counter contributes to the result
                // Count it and also take the max from all other evaluated letters, since
                // the only required info, is the number of words (regardless of the letter)
                resultForThisTestCase = std::max(resultForThisTestCase, counterIndex + 1);
            }
        }  // And this is the result . . .
        std::cout << resultForThisTestCase << '\n';
    }
    return 0;
}

c++ - 对自定义 2D 矢量进行排序会引发运行时错误。我该如何解决？

问题描述

解决方案

推荐阅读