第四章排序 AcWing 1502. PAT 排名

灰太狼 2023-09-24 13:55 62阅读 0赞

## 第四章 排序 AcWing 1502. PAT 排名 ##

### 原题链接 ###

[AcWing 1502. PAT 排名][AcWing 1502. PAT]

### 算法标签 ###

排序

### 思路 ###

依题意模拟

### 代码 ###

#pragma GCC optimize(2)
    #pragma GCC optimize(3)
    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    #define x first
    #define y second
    #define ump unordered_map
    #define pq priority_queue
    #define pii pair<int, int>
    #define rep(i, a, b) for(int i=a; i<b; ++i)
    #define Rep(i, a, b) for(int i=a; i>=b; --i)
    #define debug(a) cout<<#a<<"="<<a<<endl;
    #define debugi(i) printf("i = %lld\n", i)
    const int N=10005;
    int n, m;
    ump<string, vector<int>> gra;
    vector<int> q[4];
    inline int rd(){
        int s=0, w=1;
        char ch=getchar();
        while(ch<'0'||ch>'9'){
            if(ch=='-'){
                w=-1;    
            }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            s=s*10+ch-'0';
            ch=getchar();
        }
        return s*w;
    }
    struct Exam{
        string id;
        int score, final_rank, location_number, local_rank;
    }exam[100*300];
    bool cmp(Exam A, Exam B){
        if(A.score==B.score){
            return A.id<B.id;
        }
        else{
            return A.score>B.score;
        }
    }
    signed main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        int n;
        cin>>n;
        int l=0, r=0;
        rep(i, 0, n){
            int m;
            cin>>m;
            r+=m;
            rep(j, l, r){
                string id;
                int score;
                cin>>id>>score;
                exam[j].id=id, exam[j].score=score, exam[j].location_number=i+1;
            }
            sort(exam+l, exam+r, cmp);
            rep(j, l, r){
                int l0=l, r0=r-1;
                while(l0<r0){
                    int mid=(l0+r0)>>1;
                    if(exam[j].score<exam[mid].score){
                        l0=mid+1;
                    }else{
                        r0=mid;
                    }
                }
                exam[j].local_rank=l0-l+1;
            }
            l+=m;
        }
        cout<<l<<"\n";
        sort(exam, exam+l, cmp);
        rep(i, 0, l){
            int l0=0, r0=l-1;
            while(l0<r0){
                int mid=(l0+r0)>>1;
                if(exam[i].score<exam[mid].score){
                    l0=mid+1;
                }else{
                    r0=mid;
                }
            }
            exam[i].final_rank=l0+1;
            cout<<exam[i].id<<" "<<exam[i].final_rank<<" "<<exam[i].location_number<<" "<<exam[i].local_rank<<"\n";
        }
        return 0;
    }

### 总结 ###

1 `lower_bound`与`upper_bound`不支持自定义排序，因此对于本题 ， 需要手写二分  
2 二分模板

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用， 即记录该数值第一次出现位置：
    int bsearch_1(int l, int r)
    {
        while (l < r)
        {
            int mid = l + r >> 1;
            if (check(mid)) r = mid;    // check()判断mid是否满足性质
            else l = mid + 1;
        }
        return l;
    }

// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用， 即记录该数值最后一次出现位置：
    
    int bsearch_2(int l, int r)
    {
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (check(mid)) l = mid;
            else r = mid - 1;
        }
        return l;
    }

原创不易  
转载请标明出处  
如果对你有所帮助 别忘啦点赞支持哈  
![在这里插入图片描述][9cb4cb80a18345158f8a69e2f196e5b9.png]

[AcWing 1502. PAT]: https://www.acwing.com/problem/content/1504/
[9cb4cb80a18345158f8a69e2f196e5b9.png]: https://img-blog.csdnimg.cn/9cb4cb80a18345158f8a69e2f196e5b9.png