第四章排序 1 AcWing 1484. 最佳排名

我就是我 2024-04-07 12:40 33阅读 0赞

## 第四章 排序 1 AcWing 1484. 最佳排名 ##

#### 我的思路 ####

模拟, 进行四次排序， 依据优先级取排名最优排名及学科

#### 算法 ####

快排 暴力枚举

#### Time Limit Exceeded ####

数据 4/10

#pragma GCC optimize(2)
    #pragma GCC optimize(3)
    #include<bits/stdc++.h>
    #define int long long
    #define x first
    #define y second
    #define ump unordered_map
    #define pq priority_queue
    #define rep(i, a, b) for(int i=a;i<b;++i)
    #define Rep(i, a, b) for(int i=a;i>b;--i)
    using namespace std;
    typedef pair<int, int> PII;
    const int N=2005;
    //int t, n, m, cnt, ans; 
    int n,m;
    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;
    }
    void put(int x) {
        if(x<0) putchar('-'),x=-x;
        if(x>=10) put(x/10);
        putchar(x%10^48);
    }
    struct Stu{
        string id;
        int a, b, c, d;
    }stu[N];
    bool cmpA(Stu A, Stu B){
        return A.a>B.a;
    }
    bool cmpB(Stu A, Stu B){
        return A.b>B.b;
    }
    bool cmpC(Stu A, Stu B){
        return A.c>B.c;
    }
    bool cmpD(Stu A, Stu B){
        return A.d>B.d;
    }
    
    
    signed main(){
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	cout.tie(0);
    	cin>>n>>m;
    	rep(i, 0, n){
    	    cin>>stu[i].id>>stu[i].a>>stu[i].b>>stu[i].c;
    	    stu[i].d=(stu[i].a+stu[i].b+stu[i].c)/3.+0.5;
    	}
    	while(m--){
    	    string ID;
    	    cin>>ID;
    	    int mn=2005;
    	    char c;
    	    sort(stu, stu+n, cmpC);
    	    rep(i, 0, n){
    	        if(stu[i].id==ID){
    	            int t=stu[i].c;
    	            while(i&&t==stu[i-1].c){
    	                i-=1;
    	            }
    	            if(i<=mn){
    	                mn=i;
    	                c='E';
    	            }
    	            break;
    	        }
    	    }
    	    sort(stu, stu+n, cmpB);
    	    rep(i, 0, n){
    	        if(stu[i].id==ID){
    	            int t=stu[i].b;
    	            while(i&&t==stu[i-1].b){
    	                i-=1;
    	            }
    	            if(i<=mn){
    	                mn=i;
    	                c='M';
    	            }
    	            break;
    	        }
    	    }
    	    sort(stu, stu+n, cmpA);
    	    rep(i, 0, n){
    	        if(stu[i].id==ID){
    	            int t=stu[i].a;
    	            while(i&&t==stu[i-1].a){
    	                i-=1;
    	            }
    	            if(i<=mn){
    	                mn=i;
    	                c='C';
    	            }
    	            break;
    	        }
    	    }
    	    sort(stu, stu+n, cmpD);
    	    rep(i, 0, n){
    	        if(stu[i].id==ID){
    	            int t=stu[i].d;
    	            while(i&&t==stu[i-1].d){
    	                i-=1;
    	            }
    	            if(i<=mn){
    	                mn=i;
    	                c='A';
    	            }
    	            break;
    	        }
    	    }
    	    if(mn!=2005){
    	        cout<<mn+1<<" "<<c<<"\n";
    	    }else{
    	        cout<<"N/A"<<"\n";
    	    }
    	 
    	}
    	return 0;
    }

## 正解 ##

### 思路 ###

将每名学生存储成一个 map 映射，键为 id 对应值为其四门成绩， vector类型的  
vector grades\[4\] 则存储四门课程所有的学生的单门课程成绩并排序  
对于每一个查询，先看 map 中是否存在该名学生，如存在分别计算出每门课程的成绩，取排名最高的一个， 对已排序的成绩二分得到对应排名

### 算法标签 ###

排序 二分

### AC代码 ###

#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;
    }
    int get_r(vector<int> &a, int x){
        int l=0, r=a.size()-1;
        while(l<r){
        // 如果 mid 下取整，在区间只有 2 22 个数的时候有 mid 的值等于 left，一旦进入分支 [mid..right] 区间不会再缩小，出现死循环。把取中间数的方式改成上取整。即l+r+1      
        	int mid=l+r+1>>1;
        	// 获取第一次出现对应下标
            if(a[mid]<=x){
                l=mid;
            }else{
                r=mid-1;
            }
        }
        return a.size()-r;
    }
    signed main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        // n=rd(), m=rd();
        cin>>n>>m;
        rep(i, 0, n){
            string id;
            cin>>id;
            int t[4]={0};
            rep(j, 1, 4){
                cin>>t[j];
                t[0]+=t[j];
            }
            t[0]=round(t[0]/3.0);
            rep(j, 0, 4){
                q[j].push_back(t[j]);
                gra[id].push_back(t[j]);
            }
        }
        rep(i, 0, 4){
            sort(q[i].begin(), q[i].end());
        }
        char names[]="ACME";
        while(m--){
            string id;
            cin>>id;
            if(gra.count(id)==0){
                cout<<"N/A\n";
            }
            else{
                int res=n+1;
                char c;
                rep(i, 0, 4){
                    int r=get_r(q[i], gra[id][i]);
                    if(r<res){
                        res=r;
                        c=names[i];
                    }
                }
                cout<<res<<' '<<c<<"\n";
            }
        }
        return 0;
    }

参考文献  
[AcWing 1477. 拼写正确（PAT甲级辅导课）y总视频讲解][AcWing 1477. _PAT_y]

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

[AcWing 1477. _PAT_y]: https://www.acwing.com/video/982/
[9cb4cb80a18345158f8a69e2f196e5b9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/eb9caf84400e48409a12e38b2ed284c9.png