【算法笔记题解】《算法笔记知识点记录》第四章——算法初步1——排序(2)

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
struct student{
    int id;
    int grade[4];
}stu[2010];
char course[4] = {'A' , 'C', 'M', 'E'};
int Rank[10000000][4] ={0};
int now;
bool cmp(student a,student b){
    return a.grade[now] > b.grade[now];
}
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i = 0;i < n;++i) {
        scanf("%d %d %d %d",&stu[i].id,&stu[i].grade[1],&stu[i].grade[2],&stu[i].grade[3]);
        stu[i].grade[0] = round((stu[i].grade[1]+stu[i].grade[2]+stu[i].grade[3])/3.0) + 0.5;
     }
    for(now = 0;now<4;now++){
        sort(stu,stu + n,cmp);
        Rank[stu[0].id][now] = 1;
        for(int i = 1;i < n;++i){
            if(stu[i].grade[now] == stu[i-1].grade[now])    Rank[stu[i].id][now] = Rank[stu[i-1].id][now];
            else Rank[stu[i].id][now] = i + 1;
        }
    }
    int query;
    while(m--){
        scanf("%d",&query);
        if(!Rank[query][0]) printf("N/A\n");
        else{
            int min=10000000,mini;
            for(int i = 0; i < 4;++i){
                if(Rank[query][i] < min){
                    min = Rank[query][i];
                    mini = i;
                }
            }
            printf("%d %c\n",min,course[mini]);
        }
    }
    return 0;
}

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct student{
    char id[17];
    int score;
    int local;
    int local_rank;
}stu[30001];
bool cmp(student a, student b){
    if(a.score != b.score)  return a.score > b.score;
    else return strcmp(a.id, b.id) < 0; 
}
int main(){
    int N, K, num = 0;
    //数据接收 并对考场内用户进行排名
    scanf("%d",&N);
    for(int i = 0; i < N; ++i){
        //获取考场内考生数据
        scanf("%d",&K);
        for( int j = 0; j < K; ++j){
            scanf("%s %d",stu[num].id,&stu[num].score);
            stu[num].local = i + 1;
            num++;
        }
        //对考场内考生进行排名
        sort(stu + num - K,stu + num, cmp);
        stu[num - K].local_rank = 1;
        for(int j = num - K + 1; j < num; ++j)
            if(stu[j].score == stu[j - 1].score)
                stu[j].local_rank = stu[j - 1].local_rank;
            else
                stu[j].local_rank = j + 1 - num +K;
    }
    printf("%d\n",num);
    sort(stu,stu + num, cmp);
    int r = 1;
    for(int i = 0; i < num; ++i){
        if(i > 0 && stu[i].score != stu[i-1].score)
            r = i + 1;
        printf("%s ",stu[i].id);
        printf("%d %d %d\n", r, stu[i].local, stu[i].local_rank);
    }
    return 0;
}

#include<stdio.h>
#include<algorithm>
#include<cstring>
using namespace std;
typedef struct Student{
    int id;
    char name[10];
    int goal;
}student;
int sorti;
bool cmp(student a,student b){
    if(sorti == 1)  return a.id < b.id;
    else if(sorti == 2) return strcmp(a.name, b.name) < 0;
    else return a.goal < b.goal;
}
int main(){
    int n;
    scanf("%d%d", &n, &sorti);
    student stu[n];
    for(int i = 0; i < n; ++i)
        scanf("%d%s%d",&stu[i].id,&stu[i].name,&stu[i].goal);
    sort(stu, stu + n, cmp);
    for(int i = 0; i < n; ++i)
        printf("%06d %s %d\n", stu[i].id, stu[i].name, stu[i].goal);
    return 0;
}

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef struct Student{
    char name[10];
    int age,worth;
}student;
bool cmp(student a, student b){
    if(a.worth != b.worth)  return a.worth > b.worth;
    else if(a.age != b.age) return a.age < b.age;
    else return strcmp(a.name,b.name) < 0;
}
int main(){
    int N,K, Age[201] = {0};
    scanf("%d%d",&N,&K);
    student stu[N];
    //读入数据
    for(int i = 0;i < N; ++i){
        scanf("%s%d%d",&stu[i].name, &stu[i].age, &stu[i].worth);
    }
    sort(stu, stu + N, cmp);
    int ansnum = 0;
    student *ans[N];
    for(int i = 0; i < N; ++i){
        if(Age[stu[i].age] < 100){
            Age[stu[i].age] ++;
            ans[ansnum ++] = &stu[i];
        }
    }
    int m ,agel, ager;
    for(int i = 1; i <= K; ++i){
        printf("Case #%d:\n",i);
        scanf("%d %d %d",&m,&agel,&ager);
        int printednum = 0;
        for(int j = 0;j < ansnum && printednum < m;++j){
            if(ans[j]->age >= agel &&ans[j]->age <= ager){
                printf("%s %d %d\n",ans[j]->name,ans[j]->age,ans[j]->worth);
                printednum ++;
            }
        }
        if(!printednum) printf("None\n");
    }
    return 0;
}

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct student{
    char name[11];  //姓名
    char id[11];    //准考证号
    int grade;      //成绩
};
bool cmp(student a, student b){//降序排列
    return a.grade > b.grade;
}
int main(){
    int n, low ,high;
    //读入所有的值
    scanf("%d",&n);
    student stu[n];
    for(int i = 0; i < n; ++i)  scanf("%s%s%d", stu[i].name, stu[i].id, &stu[i].grade);
    scanf("%d%d",&low,&high);
    sort(stu, stu + n, cmp);
    //初始化变量
    int i = 0;
    bool flag = true;
    while(stu[i].grade > high && i < n) i++;//找到第一个在范围内的元素
    while(stu[i].grade >= low && i < n){    //限制范围
        flag = false;
        printf("%s %s\n",stu[i].name, stu[i].id);
        i++;
    }
    if(flag) printf("NONE\n");
    return 0;
}

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct student{
    int GE, GI, sum;//学生成绩
    int rank, id;      //学生id和排名
    int select[6];      //选择的志愿
}stu[40010];
struct School{
    int quota;      //招生额度
    int stuNum;     //当前招生人数
    int id[40010];  //招收的考生编号
    int lastAdmit;  //最后一个招收的编号
}sch[110];
bool cmp(student a, student b){//根据要求排序
    if(a.sum != b.sum)  return a.sum > b.sum;
    else return a.GE > b.GE;
}
bool cmpID(int a, int b){
    return stu[a].id < stu[b].id;
}
int main(){
    int n, k, m;
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 0; i < m; ++i){
        scanf("%d", &sch[i].quota);//读入学校招生额度
        sch[i].lastAdmit = -1;
        sch[i].stuNum = 0;
    }
    for(int i = 0; i < n; ++i){                         //读入考生数据
        scanf("%d%d", &stu[i].GE, &stu[i].GI);
        stu[i].sum = stu[i].GE + stu[i].GI;
        stu[i].id = i;
        for(int j = 0; j < k; ++j)  scanf("%d",&stu[i].select[j]);
    }
    sort(stu, stu + n, cmp);    //排序确定名词
    for(int i = 0; i < n; ++i){
        if(i > 0&& stu[i].sum == stu[i - 1].sum && stu[i].GE == stu[i - 1].GE)  stu[i].rank = stu[i - 1].rank;
        else stu[i].rank = i;
    }
    for(int i = 0; i < n; ++i){ //对每个学生进行判定录取
        for(int j = 0; j < k; j++){
            int choice = stu[i].select[j];
            int num = sch[choice].stuNum;
            int last = sch[choice].lastAdmit;
            if(num < sch[choice].quota || (last != -1 && stu[i].rank == stu[last].rank)){//满足条件则录取
                sch[choice].id[num] = i;
                sch[choice].stuNum ++;
                sch[choice].lastAdmit = i;
                break;
            }
        }
    }
    for(int i = 0; i < m; i++){
        if(sch[i].stuNum){
            sort(sch[i].id, sch[i].id + sch[i].stuNum, cmpID);
            printf("%d",stu[sch[i].id[0]].id);
            for(int j = 1; j < sch[i].stuNum; j++)  printf(" %d",stu[sch[i].id[j]].id);
        }
        printf("\n");
    }
    return 0;   
}

#include<cstdio>
#include<cstring>
#include<string>
#include<map>
#include<algorithm>
using namespace std;
const int maxn = 10010;
struct Car{
    char id[8];
    int time;
    char status[4];
}all[maxn],valid[maxn];
int  num = 0;
map<string, int> partTime;
int timeToInt(int hh,int mm,int ss){
    return hh * 3600 + mm * 60 + ss;//使用s做单位计时
}
bool cmp(Car a, Car b){ //按照id、时间排序；
    if(strcmp(a.id,b.id))    return strcmp(a.id,b.id) < 0;
    else return a.time < b.time;
}
bool cmptime(Car a, Car b){ //按照时间排序；
    return a.time < b.time;
}
int main(){
    int n,k,hh,mm,ss;
    scanf("%d%d",&n,&k);
    for(int i = 0;i < n; ++i){      //读入记录
        scanf("%s%d:%d:%d%s",all[i].id,&hh,&mm,&ss,all[i].status);
        all[i].time = timeToInt(hh,mm,ss);
    }
    sort(all, all + n,cmp);//排序
    int maxTime = -1;//最长停留时间
    for(int i = 1;i < n;++i){
        if(!strcmp(all[i].id,all[i - 1].id) && !strcmp(all[i - 1].status,"in") && !strcmp(all[i].status,"out")){//是否满足条件
            valid[num++] = all[i - 1];
            valid[num++] = all[i];
            int inTime = all[i].time - all[i - 1].time;
            if(partTime.count(all[i].id) == 0)  partTime[all[i].id] = 0;    //无记录插入记录
            partTime[all[i].id] += inTime;                                  //计算总停车时间
            if(partTime[all[i].id] > maxTime)   maxTime = partTime[all[i].id]; //记录最大停留时间
        }
    }
    sort(valid,valid + num,cmptime);
    int now = 0,numCar = 0;
    for(int i =0;i < k;++i){                //输出当前时刻的车数
        scanf("%d:%d:%d",&hh,&mm,&ss);
        int time = timeToInt(hh,mm,ss);
        while(now < num && valid[now].time <= time){
            if(!strcmp(valid[now].status,"in"))   numCar++;
            else   numCar--;
            now ++;
        }
        printf("%d\n",numCar);
    }
    map<string, int>::iterator it;
    for(it = partTime.begin();it != partTime.end();it ++){
        if(it->second == maxTime)   printf("%s ",it->first.c_str());
    }
    printf("%02d:%02d:%02d\n",maxTime/3600,maxTime%3600/60,maxTime%60);
    return 0;
}