摘要
Title: A1025 PAT Ranking
Tag: 排序、二分
Memory Limit: 64 MB
Time Limit: 1000 ms

A1025 PAT Ranking

题意

Programming Ability Test (PAT) is organized by the College of Computer Science and Technology of Zhejiang University. Each test is supposed to run simultaneously in several places, and the ranklists will be merged immediately after the test. Now it is your job to write a program to correctly merge all the ranklists and generate the final rank.
思路

总体来说，思路比较混乱，但比较容易理解
- 首先，将录入的数据，id和grade，在分组的vector和总体的vector都存起来，用map把对应的组别记录下来（map的下标是id）
- 其次，在结构体内重载运算符，分组和总体都进行排序
- 遍历map，根据id求出其对应的grade，二分分组和总体的vector，求出对应的grade下标，就是排名
  - 这里有个注意的点，就是这里二分的选法
  - 这里是降序，而且我们想要最靠左的数的下标，所以这里还是向左二分
  - 从而可以总结出一个性质，不管数组降序还是升序，向左和向右二分，求得都是最左的和最右的
- 之后，我是又声明了一个结构体，重载运算符，输出即可

代码

/*
* @Author: NEFU AB-IN
* @Date: 2023-01-07 11:45:49
* @FilePath: \GPLT\A1025\A1025.cpp
* @LastEditTime: 2023-01-07 16:59:01
*/
#include <bits/stdc++.h>
using namespace std;
#define N n + 100
#define int long long
#define SZ(X) ((int)(X).size())
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

#undef N
const int N = 110;

#undef int

int n, k;
struct sa // 最终输出的结构体
{
    string id;
    int fr, loc, lr, gd;
    bool operator<(const sa &t) const
    {
        if (gd != t.gd)
            return gd > t.gd;
        return id < t.id;
    }
};

struct sb // 输入数据时用到的结构体
{
    string id;
    int gd;

    bool operator<(const sb &t) const
    {
        if (gd != t.gd)
            return gd > t.gd;
        return id < t.id;
    }
};

vector<sb> g[N]; // 分组
vector<sb> gg;   // 总

unordered_map<string, sa> mp;
vector<sa> ans; // 总的结果

signed main()
{
    IOS;
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        string id;
        int gd;
        cin >> k;
        for (int j = 1; j <= k; ++j)
        {
            cin >> id >> gd;
            mp[id].loc = i;
            mp[id].gd = gd;
            g[i].push_back({id, gd});
            gg.push_back({id, gd});
        }
    }

    sort(gg.begin(), gg.end());
    for (int i = 1; i <= n; ++i)
    {
        sort(g[i].begin(), g[i].end());
    }

    for (auto &[id, t] : mp)
    {
        auto loc = t.loc; // 组别
        auto gd = t.gd;   // 成绩
        // 求分组内rank

        int l = 0, r = SZ(g[loc]) - 1;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (g[loc][mid].gd <= gd)
                r = mid;
            else
                l = mid + 1;
        }
        mp[id].lr = l + 1;

        // 求总体rank
        l = 0, r = SZ(gg) - 1;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (gg[mid].gd <= gd)
                r = mid;
            else
                l = mid + 1;
        }
        mp[id].fr = l + 1;
        ans.push_back({id, t.fr, t.loc, t.lr, gd});
    }

    sort(ans.begin(), ans.end());

    cout << SZ(ans) << '\n';
    for (auto &[id, fr, loc, lr, gd] : ans)
    {
        cout << id << " " << fr << " " << loc << " " << lr << '\n';
    }

    return 0;
}

A1025 PAT Ranking

题意

思路

代码