SGU 281.Championship

题意：

　　有n（n≤50000）支队伍参加了两场比赛，分别有两个排名。现在要求输出总排名，如果对任意m，在两个排名的前m个队伍都相同，那么在总排名前m个队伍就是这些队伍。其它情况按字典序排。

Solution：

　　简单题。

　　先map定位每个队伍在第一个排名中的位置。从第二个排名的第一个开始，找到最小满足条件的m，对这m个队伍按照字典序进行排序。然后继续找新的m（不包括排完序的队伍）直到所有队伍排完。

#include <iostream>

#include <algorithm>

#include <cstring>

#include <vector>

#include <map>

using namespace std;

map<string, int> pos;

vector<string> Rank;

int n;

int main()

{

    ios::sync_with_stdio (  );

    cin >> n;

    string name;

    for ( int i = ; i <= n; ++i ) {

        cin >> name;

        pos[name] = i;

    }

    int r = , l = ;

    for ( int i = ; i <= n; ++i ) {

        cin >> name;

        Rank.push_back ( name );

        r = max ( r, pos[name] );

        if ( i == r ) {

            sort ( Rank.begin() + l, Rank.begin() + r );

            l = r;

        }

    }

    for ( int i = ; i < n; ++i ) {

        cout << Rank[i] << "\n";

    }

}

巴特西

SGU 281.Championship

最新文章

热门文章