主页 / 问题 / 1422987
Accepted
Dedalus Morffino
Asked:2022-08-23 03:44:58 +0000 UTC2022-08-23 03:44:58 +0000 UTC

请帮助解决EOlimp问题[关闭]

  • 772

所以，这就是问题本身：https ://www.eolymp.com/ru/problems/3922

这是我在伪代码中的解决方案：

function solve(input: string) -> string {
    let lines = input.split("\n");
    let n = int(lines[0]);
    
    let l = lines.length();
    for(let j = 0; j < lines.length(); j += 1) {
        if(lines[j].length() == 0) { l -= 1; }   
    }
    
    let mes: int[] = [];
    let pos: int[] = [];
    let i = 1;
    while(i < l) {
        mes.push(int(lines[i]));
        pos.push(i);
        if(int(lines[i]) == 0) { i += 3;}
        else { i += 2;}
    }
    
    let rel: int[] = [];
    for(let j = 0; j < mes.length(); j += 1) {
        rel.push(0);
    }
    
    for(let j = 0; j < mes.length(); j += 1) {
        if(mes[j] != 0) {
            if(mes[mes[j] - 1] == 0) {
                rel[mes[j] - 1] += 1;
            }
        }
    }
    
    let index = 0;
    for(let j = 0; j < rel.length(); j += 1) {
        if(rel[j] > rel[index]) {
            index = j;
        }
    }
    
    
    return lines[pos[index] + 1];
}

这里的input是一串输入数据（自然是带有光标翻译字符\n），返回时显示答案。它适用于我的样品，但发送时我会抓住 WA。也许我在某个地方遗漏了一些东西。请告诉我在哪里？）

алгоритм олимпиада

1 个回答

  1. Best Answer

    我们只是从最后开始，为这条消息的答案添加一个计数器。然后我们在零中寻找最大的计数器。

    其实，一切。没有树...

    struct Msg
{
    int no;
    string subj;
    string text;
    int    count = 0;
};

int main()
{
    int n;
    cin >> n;
    vector<Msg> m;
    for(int i = 0; i < n; ++i)
    {
        Msg s;
        cin >> s.no; cin.ignore(1000,'\n');
        if (s.no == 0) getline(cin,s.subj);
        getline(cin,s.text);
        m.push_back(s);
    }
    for(size_t i = m.size(); i-->0; )
    {
        m[i].count++;
        if (m[i].no) m[m[i].no-1].count += m[i].count;
    }

    auto it = *max_element(m.begin(),m.end(),
                           [](const Msg& a, const Msg& b)
                           {
                               if (a.no > b.no) return true;
                               if (a.no < b.no) return false;
                               return a.count < b.count;
                           });
    cout << it.subj;
}
    • 2

相关问题