排序算法刷题

2022-08-31

[[toc]]

1012 The Best Rank

思路：不知道有什么好方法，用了四次sort，对每个指标都进行了排序。

注意：成绩一样排名是一样的，没有前后顺序，因此要判断是否和前面同学一个分数。

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
const int N =2010;


char cou[4] = {'A', 'C', 'M', 'E'};
struct student {
    int id;
    int c, m, e, a;
    student(int _id, int _c, int _m, int _e, int _a):id(_id), c(_c), m(_m), e(_e), a(_a){}
};

bool cmp(student a, student b){
    return a.a > b.a;
}

bool cmp1(student a, student b){
    return a.c > b.c;
}

bool cmp2(student a, student b){
    return a.m > b.m;
}

bool cmp3(student a, student b){
    return a.e > b.e;
}
vector<student> v;
map<int, vector<int> > ma;
int main (int argc, char *argv[])
{
    int n, m;
    scanf("%d%d", &n, &m);
    int id, C, M, E;
    for (int i = 0; i < n; i++) {
        scanf("%d%d%d%d", &id, &C, &M, &E);
        v.push_back(student(id, C, M, E, (C+M+E)/3));
    }
    int lastRank;
    sort(v.begin(), v.end(), cmp);
    for (int i = 0; i < v.size(); i++) {
        if (i != 0 && v[i].a == v[i-1].a) {
            ma[v[i].id].push_back(lastRank);
        }
        else {
            ma[v[i].id].push_back(i + 1);
            lastRank = i + 1;
        }
    }
    sort(v.begin(), v.end(), cmp1);
    for (int i = 0; i < v.size(); i++) {
        if (i != 0 && v[i].c == v[i-1].c) {
            ma[v[i].id].push_back(lastRank);
        }
        else {
            ma[v[i].id].push_back(i + 1);
            lastRank = i + 1;
        }
    }
    sort(v.begin(), v.end(), cmp2);
    for (int i = 0; i < v.size(); i++) {
        if (i != 0 && v[i].m == v[i-1].m) {
            ma[v[i].id].push_back(lastRank);
        }
        else {
            ma[v[i].id].push_back(i + 1);
            lastRank = i + 1;
        }
    }
    sort(v.begin(), v.end(), cmp3);
    for (int i = 0; i < v.size(); i++) {
        if (i != 0 && v[i].e == v[i-1].e) {
            ma[v[i].id].push_back(lastRank);
        }
        else {
            ma[v[i].id].push_back(i + 1);
            lastRank = i + 1;
        }
    }
    int query;
    for (int i = 0; i < m; i++) {
        scanf("%d", &query);
        if (ma.find(query) == ma.end()) {
            printf("N/A\n");
        }
        else {
            int max = 10000;
            char course;
            for (int j = 0; j < 4; j++) {
                if (ma[query][j] < max) {
                    max = ma[query][j];
                    course = cou[j];
                }
            }
            printf("%d %c\n", max, course);
        }
    }
    return 0;
}

List Sorting

思路：一道简单的排序题，写多个cmp即可。

#include <cstdio>
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
const int N = 1e5 + 10;

struct student{
    int id;
    string name;
    int grade;
    student(int _id, string _name, int _grade):id(_id), name(_name), grade(_grade){}
};

bool cmp1(student a, student b){
    return a.id < b.id;
}

bool cmp2(student a, student b){
    return a.name != b.name ? a.name < b.name : a.id < b.id;
}

bool cmp3(student a, student b){
    return a.grade != b.grade ? a.grade < b.grade : a.id < b.id;
}

void printResult(vector<student> &v){
    for (int i = 0; i < v.size(); i++) {
        printf("%06d ", v[i].id);
        cout << v[i].name << " " << v[i].grade << endl;
    }
}

vector<student> v;
int main (int argc, char *argv[])
{
    int m, c;
    scanf("%d %d", &m, &c);
    int id, grade;
    string name;
    for (int i = 0; i < m; i++) {
        cin >> id >> name >> grade;
        v.push_back(student(id, name, grade));
    }
    if (c == 1) {
        sort(v.begin(), v.end(), cmp1);
        printResult(v);
    }
    else if (c == 2) {
        sort(v.begin(), v.end(), cmp2);
        printResult(v);
    }
    else {
        sort(v.begin(), v.end(), cmp3);
        printResult(v);
    }
    return 0;
}

1055 The World’s Richest

思路：一道简单的排序.

#include <stdio.h>
#include <algorithm>
#include <string>
#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5 + 10;

struct people {
    string name;
    int age;
    int worth;
    people(string _name, int _age, int _worth):name(_name), age(_age), worth(_worth){}
};

bool cmp(people a, people b){
    if (a.worth != b.worth) {
        return a.worth > b.worth;
    }
    else if (a.age != b.age) {
        return a.age < b.age;
    }
    else {
        return a.name < b.name;
    }
}
vector<people> v;
int main (int argc, char *argv[])
{
    int n, k;
    scanf("%d%d", &n, &k);
    string name;
    int age, worth;
    for (int i = 0; i < n; i++) {
        cin >> name >> age >> worth;
        v.push_back(people(name, age, worth));
    }
    sort(v.begin(), v.end(), cmp);
    int m, Amin, Amax;
    for (int i = 0; i < k; i++) {
        int num = 0;
        scanf("%d%d%d", &m, &Amin, &Amax);
        printf("Case #%d:\n", i + 1);
        for (int j = 0; j < v.size() && num < m; j++) {
            if (v[j].age >= Amin && v[j].age <= Amax) {
                cout << v[j].name << " " << v[j].age << " " << v[j].worth << endl;
                num ++;
            }
        }
        if (num == 0) {
            cout << "None" << endl;
        }
    }
    return 0;
}

1075 PAT Judge

思路：对数据进行排序。
注意：判断数据是否submit有效，无效不输出。以及有些-1要输出零。最重要的是要去除无效的人，无效的人要在零分人之后，不然rank会有问题。可以在cmp里加上是否有效的比价，有效的排在前面。

#include <cstdio>
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e4 + 10;

struct student {
    int id;
    int score[5] = {-2, -2, -2, -2, -2};
    int all_score = 0;
    int all_problem = 0;
}Student[N];

bool submit[N];
bool cmp(student a, student b){
    if (a.all_score != b.all_score) {
        return a.all_score > b.all_score;
    }
    else if (a.all_problem != b.all_problem) {
        return a.all_problem > b.all_problem;
    }
    else if (submit[a.id] != submit[b.id]) {
        return submit[a.id] > submit[b.id];
    }
    else {
        return a.id < b.id;
    }

}

int problem[5];
int main (int argc, char *argv[])
{
    fill(submit, submit + N, false);
    int n, k, m;
    scanf("%d%d%d", &n, &k, &m);
    for (int i = 0; i < k; i++) {
        scanf("%d", problem + i);
    }
    int id, problem_id, score;
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &id, &problem_id, &score);
        Student[id].id = id;
        if (score > Student[id].score[problem_id-1]) {
            if (score != -1) {
                Student[id].score[problem_id-1] = score;
                submit[id] = true;
            }
            if (score == -1) {
                Student[id].score[problem_id-1] = 0;
            }
            if (score == problem[problem_id-1]) {
                Student[id].all_problem++;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < k; j++) {
            if (Student[i].score[j] != -2) {
                Student[i].all_score += Student[i].score[j];
            }
        }
    }
    sort(Student + 1, Student + n + 1, cmp);
    int lastRank = 1;
    printf("%d %05d %d ", lastRank, Student[1].id, Student[1].all_score);
    for (int i = 0; i < k; i++) {
        if (Student[1].score[i] == -2) {
            printf("-");
        }
        else {
            printf("%d", Student[1].score[i]);
        }
        if (i != k - 1) {
            printf(" ");
        }
    }
    printf("\n");
    for (int i = 2; i <= n; i++) {
        if (submit[Student[i].id] == true) {
            if (Student[i].all_score == Student[i-1].all_score) {
                printf("%d %05d %d ", lastRank, Student[i].id, Student[i].all_score);
            }
            else {
                lastRank = i;
                printf("%d %05d %d ", lastRank, Student[i].id, Student[i].all_score);
            }
            for (int j = 0; j < k; j++) {
                if (Student[i].score[j] == -2) {
                    printf("-");
                }
                else {
                    printf("%d", Student[i].score[j]);
                }
                if (j != k - 1) {
                    printf(" ");
                }
            }
            printf("\n");
        }
    }
    return 0;
}