当前位置：网站首页>【小码匠自习室】[NOI Online 2020-3 入门组] 最急救助：被“幸运女神”眷顾的人

【小码匠自习室】[NOI Online 2020-3 入门组] 最急救助：被“幸运女神”眷顾的人

2022-08-08 13:52:00 【小码匠】

碎碎念

我，小码匠，作为被“幸运女神”眷顾的人，竟然只有一个case发生了排序后顺序打乱的问题!

题目地址

[NOI Online #3 入门组] 最急救助
- https://www.luogu.com.cn/problem/P6565

题目描述

救助中心每天都要收到很多求救信号。收到求救信号后，救助中心会分析求救信号，找出最紧急的求救者给予救助。

求救信号是一个由小写英文字母组成的字符串，字符串中连续三个字符依次组成sos的情况越多（即包含子串sos的数目越多），代表着求救者情况越紧急。

现在请你帮助救助中心找出最紧急的求救者。注意字符串中包含的sos可以有重叠，例如sosos算作包含 2 个sos。

输入格式

输出格式

输出到标准输出。

输出共两行，第一行是最紧急求救者的名字。如果最紧急求救者有多个，则按照输入的顺序将他们的名字依次输出，相邻两个名字间用空格分隔。

第二行一个整数，表示最紧急求救者的求救信号中包含有多少个sos子串。

输入输出样例

输入 #1

2
adam
ineedhelpsosineedhelpsos
mark
ineedmorehelpsoshelpmesossoshelpme

输出 #1

mark
3

输入 #2

3
susan
sosososososos
jack
sossossossos
allen
soshelpsossossossossos

输出 #2

susan allen
6

说明/提示

数据规模与约定

对于 10% 的数据，n=1。
对于所有数据，1≤n≤100，求救者名字长度不超过 20，求救信号长度不超过 200。

题解

小码匠题解一: 90分

AC: 9
WA: 1
- 排序后顺序被打乱，导致输出顺序不对

void coder_solution() {

    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;
    string s;
    vector<pair<int, string>> vpi(n);
    for(int i = 0; i < n; ++i) {
        cin >> vpi[i].second;
        cin >> s;
        for(int j = 0; j < s.size(); ++j) {
            if(s[j] == 's' && s[j + 1] == 'o' && s[j + 2] == 's') {
                vpi[i].first++;
            }
        }
    }
    sort(vpi.begin(), vpi.end(), greater<pair<int, string>>());
    int max = vpi[0].first;
    for(int i = 0; i < n; ++i) {
        if(vpi[i].first == max) {
            cout << vpi[i].second << "";
        } else{
            break;
        }
    }
    cout << endl;
    cout << max;
}

小码匠题解二

AC: 10

void coder_solution() {

    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n;
    cin >> n;
    string s;
    vector<pair<int, string>> vpi(n);
    int max_num = 0;
    for(int i = 0; i < n; ++i) {
        cin >> vpi[i].second;
        cin >> s;
        for(int j = 0; j < s.size(); ++j) {
            if(s[j] == 's' && s[j + 1] == 'o' && s[j + 2] == 's') {
                vpi[i].first++;
            }
        }
        max_num = max(max_num, vpi[i].first);
    }

    for(int i = 0; i < n; ++i) {
        if(vpi[i].first == max_num) {
            cout << vpi[i].second << " ";
        }
    }
    cout << endl;
    cout << max_num;
}

原网站

版权声明
本文为[小码匠]所创，转载请带上原文链接，感谢
https://cloud.tencent.com/developer/article/2068176