英文题干

The ICPC World Finals are coming. Due to some reasons, the 46th and 47th World Finals will be held simultaneously. For the teams qualified in both competitions, they should choose one to take part in.

As we know, lzr010506's team is double-qualified and should make a choice. To make a wiser choice, lzr010506 looked up the qualified lists for two competitions and trained a magic model to predict the results for all participants among the two competitions. Moreover, a result contains the number of solved problems and the time penalty. The more solved problems, the better the result is, and if two teams solved the same number of problems, the result with the lower time penalty is better.

Now, lzr010506 wants to know the best possible ranking if the actual results are all the same as predicted and that the competition choices of the double-qualified teams can be arbitrarily arranged by him.

Input:

The first line contains one integer , denoting the number of teams qualified in the 46th World Finals.

Next 𝑛 lines each contain one string and two integers , denoting the name, the predicted number of solved problems, and time penalty of one team in the 46th World Finals respectively.

Next one line contains one integer , denoting the number of teams qualified in the 47th World Finals.

Next 𝑚 lines each contain one string and two integers , denoting the name, the predicted number of solved problems, and time penalty of one team in the 47th World Finals respectively.

It is guaranteed that:

  • the team names only contain digits and English letters;

  • the team names in one competition are different from each other;

  • no two teams have the same predicted number of solved problems and the time penalty simultaneously in one competition;

  • the same names among two qualified name lists refer to the same team in real;

  • ''lzr010506'' appears in both two qualified name lists.

Output:

Output one line containing one integer, denoting the best possible ranking of lzr010506's team.

中文题干

ICPC世界总决赛即将到来。由于某些原因，第46届和第47届世界总决赛将同时举行。对于在两项比赛中都获得资格的队伍，他们应选择其中一项参加。

众所周知，lzr010506的团队获得了双重资格，需要做出选择。为了做出更明智的选择，lzr010506查看了两项比赛的入围名单，并训练了一个神奇的模型来预测两项比赛中所有参与者的结果。此外，一个结果包括解决问题的数量和时间罚时。解决的问题越多，结果越好，如果两支队伍解决问题数量相同，则时间罚时较低的结果更好。

现在，lzr010506想知道，如果实际结果与预测结果完全相同，并且双重资格的队伍的比赛选择可以由他任意安排，那么可能获得的最佳排名是什么。

思路

一道简单的排序签到题

  1. 首先分别将第46和47届的选手实力进行排序（按照解题数和罚时）。

  2. 然后分别考虑"lzr010506"参加46和47届比赛的情况，去除他参加的比赛中排在他前面的且拥有两场比赛资格的队伍，最后比较去除后他在哪场比赛的名次更高即可。

AC代码

时间复杂度：O()

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
using namespace std;
const int maxn = 1e5 + 5;

map<string, int> mp;

struct Team
{
    string name;
    int problems;
    int penalty;

    bool operator<(const Team& other) const
    {
        if (problems == other.problems)
            return penalty < other.penalty;
        return problems > other.problems;
    }
} teams_46[maxn], teams_47[maxn];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    for (int i = 1; i <= n; ++i)
    {
        cin >> teams_46[i].name >> teams_46[i].problems >> teams_46[i].penalty;
        mp[teams_46[i].name]++;
    }

    int m;
    cin >> m;

    for (int i = 1; i <= m; ++i)
    {
        cin >> teams_47[i].name >> teams_47[i].problems >> teams_47[i].penalty;
        mp[teams_47[i].name]++;
    }

    sort(teams_46 + 1, teams_46 + n + 1);
    sort(teams_47 + 1, teams_47 + m + 1);

    int rank_46 = 0;
    int cnt1 = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (mp[teams_46[i].name] == 2 && teams_46[i].name != "lzr010506")
        {
            cnt1++;
        }
        if (teams_46[i].name == "lzr010506")
        {
            rank_46 = i;
            break;
        }
    }

    int rank_47 = 0;
    int cnt2 = 0;
    for (int i = 1; i <= m; ++i)
    {
        if (mp[teams_47[i].name] == 2 && teams_47[i].name != "lzr010506")
        {
            cnt2++;
        }
        if (teams_47[i].name == "lzr010506")
        {
            rank_47 = i;
            break;
        }
    }

    int best_rank = min(rank_46 - cnt1, rank_47 - cnt2);
    cout << best_rank << endl;

    return 0;
}