数据结构Pta训练题-编程2

万字长文，整理不易。点赞加评论期末高分过！

感谢你这么帅（漂亮）​还支持我

7-8 最短工期

一个项目由若干个任务组成，任务之间有先后依赖顺序。项目经理需要设置一系列里程碑，在每个里程碑节点处检查任务的完成情况，并启动后续的任务。现给定一个项目中各个任务之间的关系，请你计算出这个项目的最早完工时间。

输入格式：
首先第一行给出两个正整数：项目里程碑的数量 N（≤100）和任务总数 M。这里的里程碑从 0 到 N−1 编号。随后 M 行，每行给出一项任务的描述，格式为“任务起始里程碑 任务结束里程碑 工作时长”，三个数字均为非负整数，以空格分隔。

输出格式：
如果整个项目的安排是合理可行的，在一行中输出最早完工时间；否则输出"Impossible"。

输入样例 1：

9 12
0 1 6
0 2 4
0 3 5
1 4 1
2 4 1
3 5 2
5 4 0
4 6 9
4 7 7
5 7 4
6 8 2
7 8 4

输出样例 1：

18

输入样例 2：

4 5
0 1 1
0 2 2
2 1 3
1 3 4
3 2 5

输出样例 2：

Impossible

解析

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int n, m, ans;
int mp[100][100];
int l[100], q[100], t[100];

int main() {
    int a, b, c, head = 0, tail = 0;
    scanf("%d%d", &n, &m);
    memset(mp, -1, sizeof(mp));
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &a, &b, &c);
        mp[a][b] = c;
        l[b]++;
    }
    for (int i = 0; i < n; i++) {
        if (!l[i]) {
            q[tail++] = i;
        }
    }
    while (head < tail) {
        int temp = q[head++];
        if (t[temp] > ans) ans = t[temp];
        for (int i = 0; i < n; i++) {
            if (mp[temp][i] != -1) {
                l[i]--;
                if (!l[i]) q[tail++] = i;
                if (t[i] < t[temp] + mp[temp][i]) {
                    t[i] = t[temp] + mp[temp][i];
                }
            }
        }
    }
    if (tail < n) printf("Impossible");
    else printf("%d", ans);
}

7-9 哈利·波特的考试

哈利·波特要考试了，他需要你的帮助。这门课学的是用魔咒将一种动物变成另一种动物的本事。例如将猫变成老鼠的魔咒是haha，将老鼠变成鱼的魔咒是hehe等等。反方向变化的魔咒就是简单地将原来的魔咒倒过来念，例如ahah可以将老鼠变成猫。另外，如果想把猫变成鱼，可以通过念一个直接魔咒lalala，也可以将猫变老鼠、老鼠变鱼的魔咒连起来念：hahahehe。

现在哈利·波特的手里有一本教材，里面列出了所有的变形魔咒和能变的动物。老师允许他自己带一只动物去考场，要考察他把这只动物变成任意一只指定动物的本事。于是他来问你：带什么动物去可以让最难变的那种动物（即该动物变为哈利·波特自己带去的动物所需要的魔咒最长）需要的魔咒最短？例如：如果只有猫、鼠、鱼，则显然哈利·波特应该带鼠去，因为鼠变成另外两种动物都只需要念4个字符；而如果带猫去，则至少需要念6个字符才能把猫变成鱼；同理，带鱼去也不是最好的选择。

输入格式:
输入说明：输入第1行给出两个正整数N (≤100)和M，其中N是考试涉及的动物总数，M是用于直接变形的魔咒条数。为简单起见，我们将动物按1~N编号。随后M行，每行给出了3个正整数，分别是两种动物的编号、以及它们之间变形需要的魔咒的长度(≤100)，数字之间用空格分隔。

输出格式:
输出哈利·波特应该带去考场的动物的编号、以及最长的变形魔咒的长度，中间以空格分隔。如果只带1只动物是不可能完成所有变形要求的，则输出0。如果有若干只动物都可以备选，则输出编号最小的那只。

输入样例:

6 11
3 4 70
1 2 1
5 4 50
2 6 50
5 6 60
1 3 70
4 6 60
3 6 80
5 1 100
2 4 60
5 2 80

输出样例:

4 70

解析

/**
 * 7-9 哈利·波特的考试
 *  最短路径     迪杰斯特拉算法
 */
#include<stdio.h>
#include<string.h>

#define maxInt 2147483647

typedef struct {
    int arcs[102][102];
    int vexnum, arcnum;
} MGraph;

int final[102];//final[w]=1表示求得顶点v0至vw的最短路径 
int D[102];  //记录v0到vi的当前最短路径长度
int P[102]; //记录v0到vi的当前最短路径vi的前驱

int i, u, j, m, v, min, w, k, a, b, c, min1 = 999999, max = -991111, p = 0;

void Dijkstra(MGraph G, int v0) {
    for (v = 0; v < G.vexnum; v++)    //初始化数据
    {
        final[v] = 0;            //全部顶点初始化为未知最短路径状态
        D[v] = G.arcs[v0][v];// 将与v0点有连线的顶点加上权值
        P[v] = -1;                //初始化路径数组P为-1
    }

    D[v0] = 0;  //v0至v0路径为0
    final[v0] = 1;    // v0至v0不需要求路径
    // 开始主循环，每次求得v0到某个v顶点的最短路径
    for (v = 1; v < G.vexnum; v++) {
        min = maxInt;    // 当前所知离v0顶点的最近距离
        for (w = 0; w < G.vexnum; w++) // 寻找离v0最近的顶点
        {
            if (!final[w] && D[w] < min) {
                k = w;
                min = D[w];    // w顶点离v0顶点更近
            }
        }
        final[k] = 1;    // 将目前找到的最近的顶点置为1
        for (w = 0; w < G.vexnum; w++) // 修正当前最短路径及距离
        {
            // 如果经过v顶点的路径比现在这条路径的长度短的话
            if (!final[w] && (min + G.arcs[k][w] < D[w])) { // 说明找到了更短的路径，修改D[w]和P[w]
                D[w] = min + G.arcs[k][w];  // 修改当前路径长度
                P[w] = k;
            }
        }
    }
}

int main() {
    MGraph G;
    memset(final, 0, sizeof(final));
    memset(D, 0x3f3f3f3f, sizeof(D));
    memset(G.arcs, 0x3f3f3f3f, sizeof(G.arcs));   //邻接矩阵一定要初始化
    scanf("%d %d", &G.vexnum, &m);
    for (i = 0; i < m; i++) {
        scanf("%d %d %d", &a, &b, &c);
        G.arcs[a - 1][b - 1] = c;
        G.arcs[b - 1][a - 1] = c;
    }
    for (u = 0; u < G.vexnum; u++) {
        max = -9999999;
        Dijkstra(G, u);
        for (j = 0; j < G.vexnum; j++) {
            if (D[j] > max)
                max = D[j];
        }
        if (max < min1) {
            min1 = max;
            p = u + 1;
        }

    }
    if (p == 0)
        printf("0");
    else
        printf("%d %d\n", p, min1);
    return 0;
}

7-10 旅游规划

有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。

输入格式:
输入说明：输入数据的第1行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0~(N−1)；M是高速公路的条数；S是出发地的城市编号；D是目的地的城市编号。随后的M行中，每行给出一条高速公路的信息，分别是：城市1、城市2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过500。输入保证解的存在。

输出格式:
在一行里输出路径的长度和收费总额，数字间以空格分隔，输出结尾不能有多余空格。

输入样例:

4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20

输出样例:

3 40

解析

#include <stdio.h>
#include <stdbool.h>
#define MAX_SIZE 500
#define INF 1000000

typedef struct {
    int city;
    int length;
    int fee;
} Road;

int dijkstra(Road graph[MAX_SIZE][MAX_SIZE], int N, int S, int D, int *path) {
    bool visited[MAX_SIZE] = {false};
    int distances[MAX_SIZE];
    int fees[MAX_SIZE];
    
    for (int i = 0; i < N; i++) {
        distances[i] = INF;
        fees[i] = INF;
        path[i] = -1;
    }
    
    distances[S] = 0;
    fees[S] = 0;
    
    for (int count = 0; count < N - 1; count++) {
        int minDist = INF;
        int minCity = -1;
        
        // 找到当前距离最小的城市
        for (int i = 0; i < N; i++) {
            if (!visited[i] && distances[i] < minDist) {
                minDist = distances[i];
                minCity = i;
            }
        }
        
        visited[minCity] = true;
        
        // 更新相邻城市的距离和费用
        for (int i = 0; i < N; i++) {
            if (!visited[i] && graph[minCity][i].city != -1) {
                int newDist = distances[minCity] + graph[minCity][i].length;
                int newFee = fees[minCity] + graph[minCity][i].fee;
                
                if (newDist < distances[i] || (newDist == distances[i] && newFee < fees[i])) {
                    distances[i] = newDist;
                    fees[i] = newFee;
                    path[i] = minCity;
                }
            }
        }
    }
    
    return distances[D];
}

int main() {
    int N, M, S, D;
    scanf("%d %d %d %d", &N, &M, &S, &D);
    
    Road graph[MAX_SIZE][MAX_SIZE];
    for (int i = 0; i < MAX_SIZE; i++) {
        for (int j = 0; j < MAX_SIZE; j++) {
            graph[i][j].city = -1;
            graph[i][j].length = -1;
            graph[i][j].fee = -1;
        }
    }
    
    for (int i = 0; i < M; i++) {
        int city1, city2, length, fee;
        scanf("%d %d %d %d", &city1, &city2, &length, &fee);
        graph[city1][city2].city = city2;
        graph[city1][city2].length = length;
        graph[city1][city2].fee = fee;
        graph[city2][city1].city = city1;
        graph[city2][city1].length = length;
        graph[city2][city1].fee = fee;
    }
    
    int path[MAX_SIZE];
    int shortestDistance = dijkstra(graph, N, S, D, path);
    int totalFee = 0;
    
    // 计算路径的总费用
    int city = D;
    while (path[city] != -1) {
        totalFee += graph[city][path[city]].fee;
        city = path[city];
    }
    
    printf("%d %d\n", shortestDistance, totalFee);
    
    return 0;
}

7-11 QQ帐户的申请与登陆

实现QQ新帐户申请和老帐户登陆的简化版功能。最大挑战是：据说现在的QQ号码已经有10位数了。

输入格式:
输入首先给出一个正整数N（≤10
5
），随后给出N行指令。每行指令的格式为：“命令符（空格）QQ号码（空格）密码”。其中命令符为“N”（代表New）时表示要新申请一个QQ号，后面是新帐户的号码和密码；命令符为“L”（代表Login）时表示是老帐户登陆，后面是登陆信息。QQ号码为一个不超过10位、但大于1000（据说QQ老总的号码是1001）的整数。密码为不小于6位、不超过16位、且不包含空格的字符串。

输出格式:
针对每条指令，给出相应的信息：

1）若新申请帐户成功，则输出“New: OK”；

2）若新申请的号码已经存在，则输出“ERROR: Exist”；

3）若老帐户登陆成功，则输出“Login: OK”；

4）若老帐户QQ号码不存在，则输出“ERROR: Not Exist”；

5）若老帐户密码错误，则输出“ERROR: Wrong PW”。

输入样例:

5
L 1234567890 myQQ@qq.com
N 1234567890 myQQ@qq.com
N 1234567890 myQQ@qq.com
L 1234567890 myQQ@qq
L 1234567890 myQQ@qq.com

输出样例:

ERROR: Not Exist
New: OK
ERROR: Exist
ERROR: Wrong PW
Login: OK

解析

/**
 * 7-11 QQ帐户的申请与登陆
 *  哈希表  分离链接法
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

/*账号与密码最大长度的定义
它们的最大长度需要比题目所给的大一位
这是因为还需要一个位置来储存'\0'来判断字符串的结尾*/
#define Max_Password_Len 17
#define Max_Account_Len 11
#define MaxTableSize 1000000

/*各种状态的定义
最好用正数表示成功的状态
用负数或0表示失败的状态
这样会让强迫症看了舒服一点*/
#define ERROR_WrongPW   -2
#define ERROR_Exist     -1
#define ERROR_NOTExist  0
#define New_OK          1
#define Login_OK        2

typedef char AccountType[Max_Account_Len];//账号类型定义
typedef char PasswordType[Max_Password_Len];//密码类型定义
typedef int Index;
typedef enum {
    New, Log
} Pattern;//两种模式，新建账号与登入账号

typedef struct {
    AccountType Account;
    PasswordType Password;
} ElemType;//数据类型的定义，每个对应一个用户，内含用户的账号和密码

//链表指针的定义
typedef struct LNode *PtrToLNode;
//链表结点的定义
typedef struct LNode {
    PtrToLNode Next;
    ElemType Data;
} LNode;
typedef PtrToLNode List;//链表的定义
typedef PtrToLNode Position;//哈希表中结点位置的定义

//哈希表的定义
typedef struct TblNode *HashTable;
typedef struct TblNode {
    int TableSize;//哈希表的大小
    List Heads;//储存各个列表头节点的数组
} TblNode;

int NextPrime(int N)//返回N的下一个素数
{
    int i, P;
    P = N % 2 ? N + 2 : N + 1;
    //P为N之后的第一个奇数
    while (P < MaxTableSize) {
        for (i = (int) sqrt(P); i > 2; i--)//因为只考虑奇数，所以i为2时就结束了
            if (P % i == 0)
                break;
        if (i == 2)
            break;//i为2说明P为素数
        else
            P += 2;//i!=2说明P不是素数，则P指向下一个奇数
    }
    return P;
}

int Hash(int Key, int TableSize) {//返回Key值相对应的哈希值，即其在哈希表中的储存下标
    return Key % TableSize;
}

HashTable CreateTable(int TableSize) {    //构造空的哈希表
    HashTable H;
    int i;
    H = (HashTable) malloc(sizeof(TblNode));
    H->TableSize = NextPrime(TableSize);
    H->Heads = (List) malloc(sizeof(LNode) * H->TableSize);
    for (i = 0; i < H->TableSize; i++) {
        H->Heads[i].Data.Account[0] = '\0';
        H->Heads[i].Data.Password[0] = '\0';
        H->Heads[i].Next = NULL;
    }
    return H;
}

Position Find(HashTable H, ElemType Key) {
    Position Pos;
    Index p;
    if (strlen(Key.Account) > 5) //账号大于5位时取最后5位
        p = Hash(atoi(Key.Account +
                      strlen(Key.Account) - 5), H->TableSize);
    else//账号不大于5位则等于它本身
        p = Hash(atoi(Key.Account), H->TableSize);
    Pos = H->Heads[p].Next;
    while (Pos && strcmp(Key.Account, Pos->Data.Account))
        Pos = Pos->Next;
    return Pos;//Pos指向用户数据的位置，没有注册就返回NULL
}

int NewOrLog(HashTable H, ElemType Key, Pattern P) {    //返回状态参数
    Position Pos, NewPos;
    Index p;
    Pos = Find(H, Key);
    switch (P) {
        case Log:
            if (Pos == NULL)
                return ERROR_NOTExist;//登陆时不存在账号
            else if (strcmp(Pos->Data.Password, Key.Password) ||
                     (strlen(Key.Password) > 16 || strlen(Key.Password) < 6))
                return ERROR_WrongPW; //密码错误或格式错误
            else
                return Login_OK;//账号和密码均正确，可以登录
        case New:
            if (Pos != NULL)
                return ERROR_Exist; //新建账号时发现已经存在这样的账号了
            else {
                NewPos = (Position) malloc(sizeof(LNode));
                strcpy(NewPos->Data.Account, Key.Account);
                strcpy(NewPos->Data.Password, Key.Password);
                if (strlen(Key.Account) > 5)
                    p = Hash(atoi(Key.Account +
                                  strlen(Key.Account) - 5), H->TableSize);
                else
                    p = Hash(atoi(Key.Account), H->TableSize);
                NewPos->Next = H->Heads[p].Next;
                H->Heads[p].Next = NewPos;
                return New_OK; //插入新值并返回插入成功
            }
    }
}

void DestroyTable(HashTable H) {    //销毁哈希表
    PtrToLNode p, q;
    int i;
    for (i = 0; i < H->TableSize; i++) {
        q = H->Heads[i].Next;
        while (q) {
            p = q->Next;
            free(q);
            q = p;
        }
    }
    free(H);
}

int main(void) {
    int N, i;
    ElemType Key;
    char Input;
    Pattern P;
    HashTable H;
    scanf("%d", &N);
    H = CreateTable(2 * N);
    for (i = 0; i < N; i++) {
        scanf("\n%c %s %s", &Input, Key.Account, Key.Password);
        P = (Input == 'L') ? Log : New;
        switch (NewOrLog(H, Key, P)) {//最后根据不同返回值输出对应状态即可
            case ERROR_Exist:
                printf("ERROR: Exist\n");
                break;
            case ERROR_NOTExist:
                printf("ERROR: Not Exist\n");
                break;
            case ERROR_WrongPW:
                printf("ERROR: Wrong PW\n");
                break;
            case Login_OK:
                printf("Login: OK\n");
                break;
            case New_OK:
                printf("New: OK\n");
                break;
        }
    }
    DestroyTable(H);
    return 0;
}

7-12 人以群分

社交网络中我们给每个人定义了一个“活跃度”，现希望根据这个指标把人群分为两大类，即外向型（outgoing，即活跃度高的）和内向型（introverted，即活跃度低的）。要求两类人群的规模尽可能接近，而他们的总活跃度差距尽可能拉开。

输入格式：
输入第一行给出一个正整数N（2≤N≤10
5
）。随后一行给出N个正整数，分别是每个人的活跃度，其间以空格分隔。题目保证这些数字以及它们的和都不会超过2
31
。

输出格式：
按下列格式输出：

Outgoing #: N1
Introverted #: N2
Diff = N3

其中N1是外向型人的个数；N2是内向型人的个数；N3是两群人总活跃度之差的绝对值。

输入样例1：

10
23 8 10 99 46 2333 46 1 666 555

输出样例1：

Outgoing #: 5
Introverted #: 5
Diff = 3611

输入样例2：

13
110 79 218 69 3721 100 29 135 2 6 13 5188 85

输出样例2：

Outgoing #: 7
Introverted #: 6
Diff = 9359

解析

/**
 * 7-12 人以群分
 *  排序
 */

#include <stdio.h>
#include <stdlib.h>

int comfunc(const void *elem1, const void *elem2);

void sort_character(int *p, int n);

int main() {
    int n, i;
    int a[100001];

    scanf("%d", &n);
    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);
    qsort(a, n, sizeof(int), comfunc);
    sort_character(a, n);

    return 0;
}

int comfunc(const void *elem1, const void *elem2) {
    int *p1 = (int *) elem1;
    int *p2 = (int *) elem2;

    return *p1 - *p2;
}

void sort_character(int *p, int n) {
    int i, j, n1, n2, sum1, sum2, dif, dif1, dif2;

    sum1 = sum2 = 0;
    dif = dif1 = dif2 = 0;
    if (n % 2 == 0) {
        n1 = n2 = n / 2;
        for (i = 0; i < n1; i++)
            sum1 += p[i];
        for (i = n1; i < n; i++)
            sum2 += p[i];
        dif = abs(sum2 - sum1);
    } else {
        n1 = n2 = n / 2;
        for (i = 0; i < n1; i++)
            sum1 += p[i];
        for (i = n / 2 + 1; i < n; i++)
            sum2 += p[i];
        dif1 = abs(sum1 + p[n1] - sum2);
        dif2 = abs(sum2 + p[n2] - sum1);
        dif = (dif1 > dif2) ? dif1 : dif2;
        if (dif1 > dif2)
            n1++;
        else
            n2++;
    }
    printf("Outgoing #: %d\n", n2);
    printf("Introverted #: %d\n", n1);
    printf("Diff = %d\n", dif);

}

7-13 寻找大富翁

胡润研究院的调查显示，截至2017年底，中国个人资产超过1亿元的高净值人群达15万人。假设给出N个人的个人资产值，请快速找出资产排前M位的大富翁。

输入格式:
输入首先给出两个正整数N（≤10
6
）和M（≤10），其中N为总人数，M为需要找出的大富翁数；接下来一行给出N个人的个人资产值，以百万元为单位，为不超过长整型范围的整数。数字间以空格分隔。

输出格式:
在一行内按非递增顺序输出资产排前M位的大富翁的个人资产值。数字间以空格分隔，但结尾不得有多余空格。

输入样例:

8 3
8 12 7 3 20 9 5 18

输出样例:

20 18 12

解析

/**
 * 7-13 寻找大富翁
 *  堆排序和选择排序
 */

#include <stdio.h>   //堆排序；  注意:此算法中，下标从1开始

#define max 1000010
int num[max];

void sift(int *num, int low, int high)  //将下标为low位置上的点调到适当位置
{
    int i, j, temp;
    i = low;
    j = 2 * i;   //num[j]是num[i]的左孩子结点；
    temp = num[i];  //待调整的结点
    while (j <= high) {
        if (j < high && num[j] < num[j + 1])   //如果右孩子比较大，则把j指向右孩子，j变为2*i+1；
            ++j;
        if (temp < num[j]) {
            num[i] = num[j];    //将num[j]调整到双亲结点的位置上；
            i = j;   //修改i和j的值，以便继续向下调整；
            j = i * 2;
        } else break;     //调整结束；
    }
    num[i] = temp;   //被调整的结点放入最终位置
}

int main() {
    int n, m, i, temp, count = 0;
    scanf("%d%d", &n, &m);
    for (i = 1; i <= n; i++)
        scanf("%d", &num[i]);
    if (n < m) m = n;   //注意，有一个测试点是n小于m的情况，这时，只用排前n个;
    for (i = n / 2; i >= 1; i--)  //所有结点建立初始堆
        sift(num, i, n);
    for (i = n; i >= 2; i--)   //进行n-1次循环，完成堆排序
    {
        /*以下3句换出了根节点中的关键字，将其放入最终位置*/
        temp = num[1];
        num[1] = num[i];
        num[i] = temp;
        count++;
        if (count == 1)
            printf("%d", num[i]);
        else
            printf(" %d", num[i]);
        if (count == m) break;  //打印前m个；
        sift(num, 1, i - 1);    //减少了1个关键字的无序序列，继续调整。
    }
    if (m == n) printf(" %d", num[1]);  //当n<m的特殊情况下，上面只打印了n~2，还有最后一个下标为1的没有打印，故再打印一个。
    return 0;
}

7-14 PAT排名汇总

计算机程序设计能力考试（Programming Ability Test，简称PAT）旨在通过统一组织的在线考试及自动评测方法客观地评判考生的算法设计与程序设计实现能力，科学的评价计算机程序设计人才，为企业选拔人才提供参考标准（网址http://www.patest.cn）。

每次考试会在若干个不同的考点同时举行，每个考点用局域网，产生本考点的成绩。考试结束后，各个考点的成绩将即刻汇总成一张总的排名表。

现在就请你写一个程序自动归并各个考点的成绩并生成总排名表。

输入格式:
输入的第一行给出一个正整数N（≤100），代表考点总数。随后给出N个考点的成绩，格式为：首先一行给出正整数K（≤300），代表该考点的考生总数；随后K行，每行给出1个考生的信息，包括考号（由13位整数字组成）和得分（为[0,100]区间内的整数），中间用空格分隔。

输出格式:
首先在第一行里输出考生总数。随后输出汇总的排名表，每个考生的信息占一行，顺序为：考号、最终排名、考点编号、在该考点的排名。其中考点按输入给出的顺序从1到N编号。考生的输出须按最终排名的非递减顺序输出，获得相同分数的考生应有相同名次，并按考号的递增顺序输出。

输入样例:

2
5
1234567890001 95
1234567890005 100
1234567890003 95
1234567890002 77
1234567890004 85
4
1234567890013 65
1234567890011 25
1234567890014 100
1234567890012 85

输出样例:文章来源地址https://www.toymoban.com/news/detail-600895.html

9
1234567890005 1 1 1
1234567890014 1 2 1
1234567890001 3 1 2
1234567890003 3 1 2
1234567890004 5 1 4
1234567890012 5 2 2
1234567890002 7 1 5
1234567890013 8 2 3
1234567890011 9 2 4

解析

/**
 * 7-14 PAT排名汇总
 *  快速排序
 */
#include <stdio.h>
#include <string.h>

struct stu {
    char id[14];                //考号
    int score;                  //分数
    int kc;                     //考场
};
struct stu a[30000];

int bigger(const char *s1, const char *s2) {
    for (int i = 0; i < 13; i++)
        if (s1[i] > s2[i])
            return 1;
        else if (s1[i] < s2[i])
            return 0;
    return 1;
}

void qsort(int l, int r) {
    if (l >= r)
        return;

    int i = l;
    int j = r;

    struct stu t = a[l];
    while (i != j) {
        while (i < j && (a[j].score < t.score || a[j].score == t.score && bigger(a[j].id, t.id)))
            j--;
        while (i < j && (a[i].score > t.score || a[i].score == t.score && bigger(t.id, a[i].id)))
            i++;
        if (i < j) {
            struct stu s = a[i];
            a[i] = a[j];
            a[j] = s;
        }
    }
    a[l] = a[i];
    a[i] = t;

    qsort(l, i - 1);
    qsort(i + 1, r);

    return;
}

void Copy(int *b2, int *b1, int n) {
    for (int i = 1; i <= n; i++)
        b2[i] = b1[i];
}

int main() {
    int n, j, i, top = 0;
    scanf("%d", &n);
    for (i = 1; i <= n; i++) {
        int k;
        scanf("%d", &k);
        for (j = 0; j < k; j++) {
            char id[14];
            int score;
            scanf("%s %d", id, &score);
            a[top].score = score;
            a[top].kc = i;
            strcpy(a[top].id, id);
            top++;
        }
    }
    qsort(0, top - 1);

    int levall = 1, b1[n + 1], b2[n + 1], score = a[0].score;

    for (i = 1; i <= n; i++)
        b1[i] = 1, b2[i] = 1;
    printf("%d\n", top);
    printf("%s %d %d %d\n", a[0].id, 1, a[0].kc, 1);
    int llevall = 1;            //上一个总排名
    levall = 2;                   //总排名

    Copy(b2, b1, n);
    b1[a[0].kc]++;
    for (i = 1; i < top; i++) {
        if (a[i].score == a[i - 1].score) {
            printf("%s %d %d %d\n", a[i].id, llevall, a[i].kc, b2[a[i].kc]);
            levall++;
            b1[a[i].kc]++;
        } else {
            printf("%s %d %d %d\n", a[i].id, levall, a[i].kc, b1[a[i].kc]);
            llevall = levall;
            levall++;

            Copy(b2, b1, n);
            b1[a[i].kc]++;                    //考场的排名
        }
    }
    return 0;
}

到了这里，关于数据结构Pta训练题-编程2的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！