PTA-学校-数据结构（排序）

2-1 直接插入排序

分数 4

作者 DS课程组

单位 临沂大学

本题要求实现直接插入排序函数，待排序列的长度1<=n<=1000。

函数接口定义：

void  InsertSort(SqList L);

其中L是待排序表，使排序后的数据从小到大排列。
###类型定义：

typedef  int  KeyType;
typedef  struct {                      
  KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/                       
  int Length;      
}SqList;

裁判测试程序样例：

#include<stdio.h>
#include<stdlib.h>
typedef  int  KeyType;
typedef  struct {                      
  KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/                       
  int Length;      
}SqList;
void  CreatSqList(SqList *L);/*待排序列建立，由裁判实现，细节不表*/ 
void  InsertSort(SqList L);
int main()
{
  SqList L;
  int i;
  CreatSqList(&L);
  InsertSort(L);
  for(i=1;i<=L.Length;i++)
   {        
      printf("%d ",L.elem[i]);
    }
  return 0;
}
/*你的代码将被嵌在这里 */

输入样例：

第一行整数表示参与排序的关键字个数。第二行是关键字值 例如：

10
5 2 4 1 8 9 10 12 3 6

输出样例：

输出由小到大的有序序列，每一个关键字之间由空格隔开，最后一个关键字后有一个空格。

1 2 3 4 5 6 8 9 10 12 

解析

void InsertSort(SqList L) {
    int i, j;
    // 从第2个元素（i=2）开始插入，i=1的元素本身是有序的
    for (i = 2; i <= L.Length; ++i) {
        // 若当前元素比前一个元素小，说明需要插入到已排序序列中
        if (L.elem[i] < L.elem[i-1]) {
            L.elem[0] = L.elem[i];  // 哨兵存储当前待插入元素（避免越界+简化移动）
            // 从已排序序列尾部向前找插入位置，同时移动元素
            for (j = i - 1; L.elem[j] > L.elem[0]; --j) {
                L.elem[j+1] = L.elem[j];  // 元素后移一位
            }
            L.elem[j+1] = L.elem[0];  // 插入到正确位置
        }
    }
}

2-2 希尔排序的实现

分数 4

作者 DS课程组

单位 临沂大学

本题要求实现一趟希尔排序函数，待排序列的长度1<=n<=1000。

函数接口定义：

void  ShellInsert(SqList L,int dk);

其中L是待排序表，使排序后的数据从小到大排列。
###类型定义：

typedef  int  KeyType;
typedef  struct {                      
  KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/                       
  int Length;      
}SqList;

裁判测试程序样例：

#include<stdio.h>
#include<stdlib.h>
typedef  int  KeyType;
typedef  struct {                      
  KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/                       
  int Length;      
}SqList;
void  CreatSqList(SqList *L);/*待排序列建立，由裁判实现，细节不表*/ 
void  ShellInsert(SqList L,int dk);
void  ShellSort(SqList L);

int main()
{
  SqList L;
  int i;
  CreatSqList(&L);
  ShellSort(L);
  for(i=1;i<=L.Length;i++)
   {        
     printf("%d ",L.elem[i]);
   }
  return 0;
}
void   ShellSort(SqList L)
{
  /*按增量序列dlta[0…t-1]对顺序表L作Shell排序,假设规定增量序列为5,3,1*/
   int k;
   int dlta[3]={5,3,1};
   int t=3;
   for(k=0;k<t;++k)
       ShellInsert(L,dlta[k]);
} 
/*你的代码将被嵌在这里 */

输入样例：

第一行整数表示参与排序的关键字个数。第二行是关键字值 例如：

10
5 2 4 1 8 9 10 12 3 6

输出样例：

输出由小到大的有序序列，每一个关键字之间由空格隔开，最后一个关键字后有一个空格。

1 2 3 4 5 6 8 9 10 12 

解析

void ShellInsert(SqList L, int dk) {
    int i, j;
    // 遍历所有需要插入的元素（从 dk+1 开始，覆盖所有子序列）
    for (i = dk + 1; i <= L.Length; ++i) {
        // 若当前元素比其所在子序列的前一个元素小，需要插入到子序列的有序部分
        if (L.elem[i] < L.elem[i - dk]) {
            L.elem[0] = L.elem[i];  // 哨兵存储当前待插入元素
            // 子序列内向前找插入位置，步长为 dk，同时移动元素
            for (j = i - dk; j > 0 && L.elem[j] > L.elem[0]; j -= dk) {
                L.elem[j + dk] = L.elem[j];  // 元素后移 dk 位
            }
            L.elem[j + dk] = L.elem[0];  // 插入到子序列的正确位置
        }
    }
}

2-3 冒泡排序

分数 4

作者 DS课程组

单位 临沂大学

本题要求实现冒泡排序函数，待排序列的长度1<=n<=1000。

函数接口定义：

void bubble_sort(SqList L)；

其中L是待排序表，使排序后的数据从小到大排列。
###类型定义：

typedef  int  KeyType;
typedef  struct {                      
  KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/                       
  int Length;      
}SqList;

裁判测试程序样例：

#include<stdio.h>
#include<stdlib.h>
typedef  int  KeyType;
typedef  struct {                      
  KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/                       
  int Length;      
}SqList;
void  CreatSqList(SqList *L);/*待排序列建立，由裁判实现，细节不表*/ 
void bubble_sort(SqList L);
int main()
{
  SqList L;
  int i;
  CreatSqList(&L);
  bubble_sort( L);
  for(i=1;i<=L.Length;i++)
   {        
     printf("%d ",L.elem[i]);  
   }
  return 0;
}
/*你的代码将被嵌在这里 */

输入样例：

第一行整数表示参与排序的关键字个数。第二行是关键字值 例如：

10
5 2 4 1 8 9 10 12 3 6

输出样例：

输出由小到大的有序序列，每一个关键字之间由空格隔开，最后一个关键字后有一个空格。

1 2 3 4 5 6 8 9 10 12 

解析

void bubble_sort(SqList L) {
    int i, j;
    int flag; // 交换标志：0=未交换，1=已交换（优化用）
    // 最多需要 L.Length-1 趟排序（n个元素需n-1趟确定所有位置）
    for (i = 1; i < L.Length; ++i) {
        flag = 0; // 初始化为未交换
        // 每趟排序后，末尾i个元素已有序，无需比较
        for (j = 1; j <= L.Length - i; ++j) {
            // 相邻元素逆序，交换位置（从小到大排序）
            if (L.elem[j] > L.elem[j + 1]) {
                int temp = L.elem[j];
                L.elem[j] = L.elem[j + 1];
                L.elem[j + 1] = temp;
                flag = 1; // 标记发生交换
            }
        }
        // 若当前趟无交换，说明序列已完全有序，提前退出
        if (flag == 0) {
            break;
        }
    }
}

2-4 快速排序

分数 4

作者 DS课程组

单位 临沂大学

本题要求实现快速排序的一趟划分函数，待排序列的长度1<=n<=1000。

函数接口定义：

int Partition ( SqList L, int low,  int high )；

其中L是待排序表，使排序后的数据从小到大排列。
###类型定义：

typedef  int  KeyType;
typedef  struct 
{                      
  KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/                       
  int Length;      
}SqList;

裁判测试程序样例：

#include<stdio.h>
#include<stdlib.h>
typedef  int  KeyType;
typedef  struct 
{                      
  KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/                     
  int Length;      
}SqList;
void  CreatSqList(SqList *L);/*待排序列建立，由裁判实现，细节不表*/ 
int Partition ( SqList  L,int low,  int  high );
void Qsort ( SqList  L,int low,  int  high );
int main()
{
  SqList L;
  int i;
  CreatSqList(&L);
  Qsort(L,1,L.Length);
  for(i=1;i<=L.Length;i++)
      printf("%d ",L.elem[i]);
  return 0;
}
void Qsort ( SqList  L,int low,  int  high ) 
{ 
    int  pivotloc;
    if(low<high)
    {  
        pivotloc = Partition(L, low, high ) ;
        Qsort (L, low, pivotloc-1) ; 
        Qsort (L, pivotloc+1, high );
     }
}
/*你的代码将被嵌在这里 */

输入样例：

第一行整数表示参与排序的关键字个数。第二行是关键字值 例如：

10
5 2 4 1 8 9 10 12 3 6

输出样例：

输出由小到大的有序序列，每一个关键字之间由空格隔开，最后一个关键字后有一个空格。

1 2 3 4 5 6 8 9 10 12 

解析

int Partition(SqList L, int low, int high) {
    KeyType pivot = L.elem[high];  // 选择最右侧元素作为基准
    int i = low - 1;               // i指向小于等于基准区域的末尾
    
    for (int j = low; j < high; j++) {
        if (L.elem[j] <= pivot) {  // 找到小于等于基准的元素
            i++;                   // 扩展小于等于基准的区域
            // 交换i和j位置的元素
            KeyType temp = L.elem[i];
            L.elem[i] = L.elem[j];
            L.elem[j] = temp;
        }
    }
    
    // 将基准元素放到正确的位置（i+1）
    KeyType temp = L.elem[i + 1];
    L.elem[i + 1] = L.elem[high];
    L.elem[high] = temp;
    
    return i + 1;  // 返回基准元素的位置
}

2-5 简单选择排序

分数 4

作者 DS课程组

单位 临沂大学

本题要求实现简单选择排序函数，待排序列的长度1<=n<=1000。

函数接口定义：

void  SelectSort(SqList L);

其中L是待排序表，使排序后的数据从小到大排列。

类型定义：

typedef  int  KeyType;
typedef  struct {                      
  KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/                       
  int Length;      
}SqList;

裁判测试程序样例：

#include<stdio.h>
#include<stdlib.h>
typedef  int  KeyType;
typedef  struct {                      
  KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/                       
  int Length;      
}SqList;
void  CreatSqList(SqList *L);/*待排序列建立，由裁判实现，细节不表*/ 
void  SelectSort(SqList L);
int main()
{
  SqList L;
  int i;
  CreatSqList(&L);
  SelectSort(L);
  for(i=1;i<=L.Length;i++)
   {        
     printf("%d ",L.elem[i]);
   }
  return 0;
}
/*你的代码将被嵌在这里 */

输入样例：

第一行整数表示参与排序的关键字个数。第二行是关键字值 例如：

10
5 2 4 1 8 9 10 12 3 6

输出样例：

输出由小到大的有序序列，每一个关键字之间由空格隔开，最后一个关键字后有一个空格。

1 2 3 4 5 6 8 9 10 12 

解析

void SelectSort(SqList L) {
    int i, j, min_idx;
    // 外层循环：待排序部分的起始位置（i从1到Length-1，最后一个元素无需排序）
    for (i = 1; i < L.Length; ++i) {
        min_idx = i; // 假设当前待排序起始位置是最小元素的下标
        // 内层循环：在待排序部分（i~Length）中找最小元素的下标
        for (j = i + 1; j <= L.Length; ++j) {
            if (L.elem[j] < L.elem[min_idx]) {
                min_idx = j; // 更新最小元素的下标
            }
        }
        // 找到最小元素后，与待排序部分的第一个元素交换（避免自身交换）
        if (min_idx != i) {
            int temp = L.elem[i];
            L.elem[i] = L.elem[min_idx];
            L.elem[min_idx] = temp;
        }
    }
}

2-6 堆排序

分数 4

作者 DS课程组

单位 临沂大学

本题要求实现堆排序中的筛选函数，待排序列的长度1<=n<=1000。

函数接口定义：

void HeapAdjust( HeapType  H, int s, int m);

其中L是待排序表，使排序后的数据从小到大排列。

类型定义：

typedef  int  KeyType;
typedef  struct {                      
  KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/                       
  int Length;      
}SqList;
typedef SqList HeapType; 

裁判测试程序样例：

#include<stdio.h>
#include<stdlib.h>
typedef  int  KeyType;
typedef  struct {                      
  KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/                       
  int Length;      
}SqList;
typedef SqList HeapType; 
void  CreatSqListHeapType *L);/*待排序列建立，由裁判实现，细节不表*/ 
void HeapAdjust( HeapType  H, int s, int m);
void HeapSort( HeapType  H);
int main()
{
  HeapType L;
  int i;
  CreatSqList(&L);
  HeapSort(L);
  for(i=1;i<=L.Length;i++)
   {        
     printf("%d ",L.elem[i]);
   }
  return 0;
}
void HeapSort( HeapType  H)
{ /*堆顺序表H进行堆排序*/
  int i; KeyType rc;
  /*建立初始堆*/
  for( i=H.Length/2;i>0; i--)
   {
      HeapAdjust(H, i, H.Length);
   }
  for(i=H.Length;i>1;i--)
   {
      rc=H.elem[1];
      H.elem[1]=H.elem[i]; 
      H.elem[i]=rc;
      HeapAdjust(H, 1, i-1); 
   }
 }
/*你的代码将被嵌在这里 */

输入样例：

第一行整数表示参与排序的关键字个数。第二行是关键字值 例如：

10
5 2 4 1 8 9 10 12 3 6

输出样例：

输出由小到大的有序序列，每一个关键字之间由空格隔开，最后一个关键字后有一个空格。

1 2 3 4 5 6 8 9 10 12 

解析

void HeapAdjust(HeapType H, int s, int m) {
    KeyType rc = H.elem[s];  // 保存当前要调整的节点值（避免被覆盖）
    int j;

    // j从s的左孩子开始（完全二叉树：父节点s的左孩子=2s，右孩子=2s+1）
    // 循环向下筛选，直到j超出堆的范围（m是堆的最后一个节点下标）
    for (j = 2 * s; j <= m; j *= 2) {
        // 步骤1：找到s的左右孩子中值较大的那个（j指向较大孩子）
        if (j < m && H.elem[j] < H.elem[j + 1]) {
            j++;  // 右孩子更大，j指向右孩子
        }

        // 步骤2：判断当前节点值是否大于等于较大孩子值
        if (rc >= H.elem[j]) {
            break;  // 已满足大根堆性质，无需继续筛选
        }

        // 步骤3：将较大孩子的值上移到当前节点位置
        H.elem[s] = H.elem[j];
        s = j;  // 更新当前节点下标为较大孩子的位置，继续向下筛选
    }

    // 步骤4：将原节点值放到最终的正确位置（维持大根堆）
    H.elem[s] = rc;
}

2-7 归并排序

分数 4

作者 DS课程组

单位 临沂大学

本题要求实现二路归并排序中的归并操作，待排序列的长度1<=n<=1000。

函数接口定义：

void Merge(SqList L,int low,int m,int high);

其中L是待排序表，使排序后的数据从小到大排列。

类型定义：

#include<stdio.h>
#include<stdlib.h>
typedef  int  KeyType;
typedef  struct {                      
  KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/                       
  int Length;      
}SqList;
void  CreatSqList(SqList *L);/*待排序列建立，由裁判实现，细节不表*/ 
void  MergeSort(SqList L,int low,int high);
void Merge(SqList L,int low,int m,int high); 
int main()
{
  SqList L;
  int i;
  CreatSqList(&L);
  MergeSort(L,1,L.Length);
  for(i=1;i<=L.Length;i++)
   {        
      printf("%d ",L.elem[i]);
   }
  return 0;
}
void MergeSort(SqList L,int low,int high)  
{     
    /*用分治法进行二路归并排序*/  
    int mid;  
    if(low<high)  /*区间长度大于1*/
    {      
        mid=(low+high)/2;               /*分解*/
        MergeSort(L,low,mid);           /*递归地对low到mid序列排序 */ 
        MergeSort(L,mid+1,high);        /*递归地对mid+1到high序列排序 */ 
        Merge(L,low,mid,high);          /*归并*/  
    }  
}
/*你的代码将被嵌在这里 */

输入样例：

第一行整数表示参与排序的关键字个数。第二行是关键字值 例如：

10
5 2 4 1 8 9 10 12 3 6

输出样例：

输出由小到大的有序序列，每一个关键字之间由空格隔开，最后一个关键字后有一个空格。

1 2 3 4 5 6 8 9 10 12 

解析

void Merge(SqList L, int low, int m, int high) {
    // 1. 初始化指针和临时数组
    int i = low;          // 左子序列起始指针
    int j = m + 1;        // 右子序列起始指针
    int k = 0;            // 临时数组索引指针
    int len = high - low + 1;  // 合并区间总长度
    int *temp = (int *)malloc(len * sizeof(int));  // 临时数组，存储合并结果

    // 2. 合并两个有序子序列
    while (i <= m && j <= high) {
        if (L.elem[i] <= L.elem[j]) {
            temp[k++] = L.elem[i++];  // 左子序列元素更小，放入临时数组
        } else {
            temp[k++] = L.elem[j++];  // 右子序列元素更小，放入临时数组
        }
    }

    // 3. 处理左子序列剩余元素
    while (i <= m) {
        temp[k++] = L.elem[i++];
    }

    // 处理右子序列剩余元素
    while (j <= high) {
        temp[k++] = L.elem[j++];
    }

    // 4. 将临时数组的有序结果复制回原数组的 [low, high] 区间
    for (k = 0; k < len; k++) {
        L.elem[low + k] = temp[k];
    }

    // 5. 释放临时数组，避免内存泄漏
    free(temp);
}

3-1 排序

分数 9

作者 陈越

单位 浙江大学

给定 n 个（长整型范围内的）整数，要求输出从小到大排序后的结果。

本题旨在测试各种不同的排序算法在各种数据情况下的表现。各组测试数据特点如下：

数据1：只有1个元素；

数据2：11个不相同的整数，测试基本正确性；

数据3：103个随机整数；

数据4：104个随机整数；

数据5：105个随机整数；

数据6：105个顺序整数；

数据7：105个逆序整数；

数据8：105个基本有序的整数；

数据9：105个随机正整数，每个数字不超过1000。

输入格式:

输入第一行给出正整数 n（≤105），随后一行给出 n 个（长整型范围内的）整数，其间以空格分隔。

输出格式:

在一行中输出从小到大排序后的结果，数字间以 1 个空格分隔，行末不得有多余空格。

输入样例:

11
4 981 10 -17 0 -20 29 50 8 43 -5

输出样例:

-20 -17 -5 0 4 8 10 29 43 50 981

解析

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    // 加速输入输出（处理1e5数据必备，避免超时）
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    // 用vector存储数据（支持动态扩容，适配长整型范围）
    vector<long long> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }

    // 调用STL sort排序（默认从小到大，内部优化适配所有测试数据）
    sort(nums.begin(), nums.end());

    // 输出：避免行末多余空格（先输出第一个元素，后续元素前加空格）
    for (int i = 0; i < n; ++i) {
        if (i > 0) {
            cout << " ";
        }
        cout << nums[i];
    }

    return 0;
}

3-2 寻找大富翁

分数 9

作者 陈越

单位 浙江大学

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

输入格式:

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

输出格式:

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

输入样例:

8 3
8 12 7 3 20 9 5 18

输出样例:

20 18 12

解析

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

// 最小堆下沉调整：维护堆性质（堆顶为最小元素）
void heapify(long long heap[], int size, int i) {
    int min_idx = i; // 初始化当前节点为最小值索引
    while (1) {
        int left = 2 * i + 1;  // 左孩子索引
        int right = 2 * i + 2; // 右孩子索引
        
        // 找到当前节点及其左右孩子中的最小值索引
        if (left < size && heap[left] < heap[min_idx]) {
            min_idx = left;
        }
        if (right < size && heap[right] < heap[min_idx]) {
            min_idx = right;
        }
        
        // 若最小值不是当前节点，交换并继续下沉调整
        if (min_idx != i) {
            long long temp = heap[i];
            heap[i] = heap[min_idx];
            heap[min_idx] = temp;
            i = min_idx; // 移动到交换后的节点，继续调整
        } else {
            break; // 堆性质已满足，退出循环
        }
    }
}

// 构建最小堆：从最后一个非叶子节点向前调整
void build_min_heap(long long heap[], int size) {
    for (int i = size / 2 - 1; i >= 0; i--) {
        heapify(heap, size, i);
    }
}

int main() {
    int N, M;
    scanf("%d %d", &N, &M);
    
    // 堆数组：存储前M大的元素（M≤10，空间开销极小）
    long long *heap = (long long *)malloc(M * sizeof(long long));
    int count = 0; // 当前堆中元素个数
    
    // 读取所有资产并维护最小堆
    for (int i = 0; i < N; i++) {
        long long x;
        scanf("%lld", &x);
        
        if (count < M) {
            // 堆未满，直接加入元素
            heap[count++] = x;
            // 堆满时构建最小堆（仅需执行一次）
            if (count == M) {
                build_min_heap(heap, M);
            }
        } else {
            // 堆已满，若当前元素大于堆顶（最小的前M大元素），则替换并调整
            if (x > heap[0]) {
                heap[0] = x;
                heapify(heap, M, 0);
            }
        }
    }
    
    // 对堆中元素降序排序（冒泡排序，元素数≤10，效率无影响）
    for (int i = 0; i < count; i++) {
        for (int j = i + 1; j < count; j++) {
            if (heap[i] < heap[j]) {
                long long temp = heap[i];
                heap[i] = heap[j];
                heap[j] = temp;
            }
        }
    }
    
    // 输出结果：结尾无多余空格
    for (int i = 0; i < count; i++) {
        if (i > 0) {
            printf(" ");
        }
        printf("%lld", heap[i]);
    }
    printf("\n");
    
    free(heap); // 释放堆内存，避免泄漏
    return 0;
}

3-3 统计工龄

分数 9

作者 陈越

单位 浙江大学

给定公司 n 名员工的工龄，要求按工龄增序输出每个工龄段有多少员工。

输入格式:

输入首先给出正整数 n（≤105），即员工总人数；随后给出 n 个整数，即每个员工的工龄，范围在 [0, 50]。

输出格式:

按工龄的递增顺序输出每个工龄的员工个数，格式为：“工龄:人数”。每项占一行。如果人数为 0 则不输出该项。

输入样例:

8
10 2 0 5 7 2 5 2

输出样例:

0:1
2:3
5:2
7:1
10:1

解析

#include <iostream>
using namespace std;

int main() {
    // 加速输入输出（处理1e5数据必备，避免超时）
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    const int MAX_AGE = 50; // 工龄最大范围（题目规定[0,50]）
    int count[MAX_AGE + 1] = {0}; // 计数数组：count[age]记录工龄age的员工数

    int n;
    cin >> n;

    // 统计每个工龄的出现次数
    for (int i = 0; i < n; ++i) {
        int age;
        cin >> age;
        count[age]++; // 对应工龄的计数+1
    }

    // 按工龄递增顺序输出（0~50），仅输出人数>0的项
    for (int age = 0; age <= MAX_AGE; ++age) {
        if (count[age] > 0) {
            cout << age << ":" << count[age] << "\n";
        }
    }

    return 0;
}

3-4 奥运排行榜

分数 9

作者 陈越

单位 浙江大学

每年奥运会各大媒体都会公布一个排行榜，但是细心的读者发现，不同国家的排行榜略有不同。比如中国金牌总数列第一的时候，中国媒体就公布“金牌榜”；而美国的奖牌总数第一，于是美国媒体就公布“奖牌榜”。如果人口少的国家公布一个“国民人均奖牌榜”，说不定非洲的国家会成为榜魁…… 现在就请你写一个程序，对每个前来咨询的国家按照对其最有利的方式计算它的排名。

输入格式:

输入的第一行给出两个正整数N和M（≤224，因为世界上共有224个国家和地区），分别是参与排名的国家和地区的总个数、以及前来咨询的国家的个数。为简单起见，我们把国家从0 ~ N−1编号。之后有N行输入，第i行给出编号为i−1的国家的金牌数、奖牌数、国民人口数（单位为百万），数字均为[0,1000]区间内的整数，用空格分隔。最后面一行给出M个前来咨询的国家的编号，用空格分隔。

输出格式:

在一行里顺序输出前来咨询的国家的排名:计算方式编号。其排名按照对该国家最有利的方式计算；计算方式编号为：金牌榜=1，奖牌榜=2，国民人均金牌榜=3，国民人均奖牌榜=4。输出间以空格分隔，输出结尾不能有多余空格。

若某国在不同排名方式下有相同名次，则输出编号最小的计算方式。

输入样例:

4 4
51 100 1000
36 110 300
6 14 32
5 18 40
0 1 2 3

输出样例:

1:1 1:2 1:3 1:4

解析

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 定义国家结构体
struct Country {
    int gold;   // 金牌数
    int total;  // 奖牌总数
    int pop;    // 人口
    int ranks[5]; // 存储4种排名，下标1-4分别对应题目要求的4种方式
};

int main() {
    int N, M;
    if (!(cin >> N >> M)) return 0;

    // 存储所有国家的数据，下标即为国家ID
    vector<Country> countries(N);
    for (int i = 0; i < N; ++i) {
        cin >> countries[i].gold >> countries[i].total >> countries[i].pop;
    }

    // 用于排序的索引数组，初始化为 0 到 N-1
    vector<int> indices(N);

    // 循环处理 4 种排名方式
    // m=1: 金牌, m=2: 奖牌, m=3: 人均金牌, m=4: 人均奖牌
    for (int m = 1; m <= 4; ++m) {
        // 重置索引
        for (int i = 0; i < N; ++i) indices[i] = i;

        // 根据当前的排名方式进行排序
        sort(indices.begin(), indices.end(), [&](int a, int b) {
            if (m == 1) return countries[a].gold > countries[b].gold;
            if (m == 2) return countries[a].total > countries[b].total;
            // 对于人均数据，使用交叉相乘避免精度损失: a/b > c/d  <=>  a*d > c*b
            if (m == 3) {
                return (long long)countries[a].gold * countries[b].pop > (long long)countries[b].gold * countries[a].pop;
            }
            // m == 4
            return (long long)countries[a].total * countries[b].pop > (long long)countries[b].total * countries[a].pop;
        });

        // 根据排序结果计算排名
        countries[indices[0]].ranks[m] = 1;
        for (int i = 1; i < N; ++i) {
            int curID = indices[i];
            int prevID = indices[i-1];
            
            bool isTied = false;
            if (m == 1) isTied = (countries[curID].gold == countries[prevID].gold);
            else if (m == 2) isTied = (countries[curID].total == countries[prevID].total);
            else if (m == 3) {
                isTied = ((long long)countries[curID].gold * countries[prevID].pop == (long long)countries[prevID].gold * countries[curID].pop);
            } else {
                isTied = ((long long)countries[curID].total * countries[prevID].pop == (long long)countries[prevID].total * countries[curID].pop);
            }

            if (isTied) {
                // 如果数值相等，排名与前一名相同
                countries[curID].ranks[m] = countries[prevID].ranks[m];
            } else {
                // 否则排名为当前的序号 + 1 (1-based index)
                countries[curID].ranks[m] = i + 1;
            }
        }
    }

    // 处理查询
    for (int i = 0; i < M; ++i) {
        int queryID;
        cin >> queryID;

        int bestRank = N + 1; // 初始化一个比最大排名N还要大的数
        int bestMethod = 1;

        // 检查4种方式，找出最优排名
        // 由于是从 m=1 到 4 遍历，且仅当 found < best 时才更新，
        // 所以自然满足"相同名次输出编号最小的计算方式"的要求
        for (int m = 1; m <= 4; ++m) {
            if (countries[queryID].ranks[m] < bestRank) {
                bestRank = countries[queryID].ranks[m];
                bestMethod = m;
            }
        }

        if (i > 0) cout << " ";
        cout << bestRank << ":" << bestMethod;
    }
    
    return 0;
}

3-5 PAT排名汇总

分数 9

作者 陈越

单位 浙江大学

计算机程序设计能力考试（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
1234567890033 95
1234567890002 77
1234567890004 85
4
1234567890013 95
1234567890011 25
1234567890014 100
1234567890042 95

输出样例:

9
1234567890005 1 1 1
1234567890014 1 2 1
1234567890001 3 1 2
1234567890013 3 2 2
1234567890033 3 1 2
1234567890042 3 2 2
1234567890004 7 1 4
1234567890002 8 1 5
1234567890011 9 2 4

解析

#include <bits/stdc++.h>
using namespace std;

struct Student {
    string id;
    int score;
    int location;      // 考点编号（1~N）
    int local_rank;    // 本考点排名
    int final_rank;    // 最终排名
};

bool cmp(const Student &a, const Student &b) {
    if (a.score != b.score) return a.score > b.score;
    return a.id < b.id;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    vector<Student> all; // 汇总所有考生

    for (int loc = 1; loc <= N; loc++) {
        int K;
        cin >> K;

        vector<Student> local(K);
        for (int i = 0; i < K; i++) {
            cin >> local[i].id >> local[i].score;
            local[i].location = loc;
        }

        // 按要求排序：分数降序，ID升序
        sort(local.begin(), local.end(), cmp);

        // 计算本考点排名（local_rank）
        local[0].local_rank = 1;
        for (int i = 1; i < K; i++) {
            if (local[i].score == local[i - 1].score)
                local[i].local_rank = local[i - 1].local_rank;
            else
                local[i].local_rank = i + 1;
        }

        // 加入总名单
        for (auto &x : local) all.push_back(x);
    }

    // 排序得到最终排名
    sort(all.begin(), all.end(), cmp);

    // 最终排名 final_rank
    all[0].final_rank = 1;
    for (int i = 1; i < (int)all.size(); i++) {
        if (all[i].score == all[i - 1].score)
            all[i].final_rank = all[i - 1].final_rank;
        else
            all[i].final_rank = i + 1;
    }

    // 输出
    cout << all.size() << "\n";
    for (auto &x : all) {
        cout << x.id << " "
             << x.final_rank << " "
             << x.location << " "
             << x.local_rank << "\n";
    }

    return 0;
}

3-6 抢红包

分数 9

作者 陈越

单位 浙江大学

没有人没抢过红包吧…… 这里给出N个人之间互相发红包、抢红包的记录，请你统计一下他们抢红包的收获。

输入格式：

输入第一行给出一个正整数N（≤104），即参与发红包和抢红包的总人数，则这些人从1到N编号。随后N行，第i行给出编号为i的人发红包的记录，格式如下：

K**N1P1⋯NKP**K

其中K（0≤K≤20）是发出去的红包个数，N**i是抢到红包的人的编号，P**i（>0）是其抢到的红包金额（以分为单位）。注意：对于同一个人发出的红包，每人最多只能抢1次，不能重复抢。

输出格式：

按照收入金额从高到低的递减顺序输出每个人的编号和收入金额（以元为单位，输出小数点后2位）。每个人的信息占一行，两数字间有1个空格。如果收入金额有并列，则按抢到红包的个数递减输出；如果还有并列，则按个人编号递增输出。

输入样例：

10
3 2 22 10 58 8 125
5 1 345 3 211 5 233 7 13 8 101
1 7 8800
2 1 1000 2 1000
2 4 250 10 320
6 5 11 9 22 8 33 7 44 10 55 4 2
1 3 8800
2 1 23 2 123
1 8 250
4 2 121 4 516 7 112 9 10

输出样例：

1 11.63
2 3.63
8 3.63
3 2.11
7 1.69
6 -1.67
9 -2.18
10 -3.26
5 -3.26
4 -12.32

解析

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;

// 存储每个人的信息：编号、净收入（分）、抢到的红包个数
struct Person {
    int id;
    long long income; // 用long long避免金额溢出（单位：分）
    int count;        // 抢到的红包个数

    Person() : id(0), income(0), count(0) {}
    Person(int _id) : id(_id), income(0), count(0) {}
};

int main() {
    // 加速输入输出（处理1e4规模数据必备）
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    // 初始化N个人（编号1~N）
    vector<Person> people(N + 1);
    for (int i = 1; i <= N; ++i) {
        people[i].id = i;
    }

    // 处理每个人发红包的记录
    for (int i = 1; i <= N; ++i) {
        int K;
        cin >> K;
        long long sum_paid = 0; // 当前人发出的总金额（分）

        for (int j = 0; j < K; ++j) {
            int ni, pi;
            cin >> ni >> pi; // ni：抢到红包的人，pi：红包金额（分）
            sum_paid += pi;
            people[ni].income += pi; // 抢到红包的人收入增加
            people[ni].count++;      // 抢到的红包个数+1
        }

        people[i].income -= sum_paid; // 发红包的人支出总金额，收入减少
    }

    // 按规则排序：收入降序 → 抢红包个数降序 → 编号升序
    sort(people.begin() + 1, people.end(), [](const Person& a, const Person& b) {
        if (a.income != b.income) {
            return a.income > b.income;
        } else if (a.count != b.count) {
            return a.count > b.count;
        } else {
            return a.id < b.id;
        }
    });

    // 输出结果（金额转元，保留两位小数）
    for (int i = 1; i <= N; ++i) {
        printf("%d %.2f\n", people[i].id, people[i].income / 100.0);
    }

    return 0;
}

3-7 点赞狂魔

分数 9

作者 陈越

单位 浙江大学

微博上有个“点赞”功能，你可以为你喜欢的博文点个赞表示支持。每篇博文都有一些刻画其特性的标签，而你点赞的博文的类型，也间接刻画了你的特性。然而有这么一种人，他们会通过给自己看到的一切内容点赞来狂刷存在感，这种人就被称为“点赞狂魔”。他们点赞的标签非常分散，无法体现出明显的特性。本题就要求你写个程序，通过统计每个人点赞的不同标签的数量，找出前3名点赞狂魔。

输入格式：

输入在第一行给出一个正整数N（≤100），是待统计的用户数。随后N行，每行列出一位用户的点赞标签。格式为“Name K F1⋯F**K”，其中Name是不超过8个英文小写字母的非空用户名，1≤K≤1000，F**i（i=1,⋯,K）是特性标签的编号，我们将所有特性标签从 1 到 107 编号。数字间以空格分隔。

输出格式：

统计每个人点赞的不同标签的数量，找出数量最大的前3名，在一行中顺序输出他们的用户名,其间以1个空格分隔,且行末不得有多余空格。如果有并列，则输出标签出现次数平均值最小的那个，题目保证这样的用户没有并列。若不足3人，则用-补齐缺失，例如mike jenny -就表示只有2人。

输入样例：

5
bob 11 101 102 103 104 105 106 107 108 108 107 107
peter 8 1 2 3 4 3 2 5 1
chris 12 1 2 3 4 5 6 7 8 9 1 2 3
john 10 8 7 6 5 4 3 2 1 7 5
jack 9 6 7 8 9 10 11 12 13 14

输出样例：

jack chris john

解析

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

// 用户信息结构体
typedef struct {
    char name[9];  // 用户名（最多8个小写字母+结束符）
    int K;         // 总点赞数
    int unique_cnt; // 不同标签数量
} User;

// 辅助函数：用于标签数组排序（升序）
int cmp_int(const void *a, const void *b) {
    return *(int *)a - *(int *)b;
}

// 自定义排序函数：按规则排序用户
int cmp_user(const void *a, const void *b) {
    User *u1 = (User *)a;
    User *u2 = (User *)b;
    
    // 首要规则：不同标签数降序
    if (u1->unique_cnt != u2->unique_cnt) {
        return u2->unique_cnt - u1->unique_cnt;
    } else {
        // 次要规则：平均值升序（交叉相乘避免浮点数精度问题）
        long long avg1 = (long long)u1->K * u2->unique_cnt;
        long long avg2 = (long long)u2->K * u1->unique_cnt;
        return avg1 - avg2; // avg1 < avg2 时返回负数，u1排在前面
    }
}

int main() {
    int N;
    scanf("%d", &N);
    User users[100]; // 最多100个用户，无需动态分配
    
    // 读取并处理每个用户
    for (int i = 0; i < N; i++) {
        char name[9];
        int K;
        scanf("%s %d", name, &K);
        
        // 读取K个标签并存储
        int tags[1000];
        for (int j = 0; j < K; j++) {
            scanf("%d", &tags[j]);
        }
        
        // 排序标签，方便去重
        qsort(tags, K, sizeof(int), cmp_int);
        
        // 统计不同标签数量
        int unique = 1; // K≥1，至少1个不同标签
        for (int j = 1; j < K; j++) {
            if (tags[j] != tags[j-1]) {
                unique++;
            }
        }
        
        // 存入用户数组
        strcpy(users[i].name, name);
        users[i].K = K;
        users[i].unique_cnt = unique;
    }
    
    // 对用户按规则排序
    qsort(users, N, sizeof(User), cmp_user);
    
    // 输出前3名，不足补"-"
    for (int i = 0; i < 3; i++) {
        if (i > 0) {
            printf(" "); // 非首个元素前加空格
        }
        if (i < N) {
            printf("%s", users[i].name);
        } else {
            printf("-");
        }
    }
    printf("\n");
    
    return 0;
}

3-8 插入排序还是归并排序

分数 9

作者 陈越

单位 浙江大学

根据维基百科的定义：

插入排序是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确的位置。如此迭代直到全部元素有序。

归并排序进行如下迭代操作：首先将原始序列看成 N 个只包含 1 个元素的有序子序列，然后每次迭代归并两个相邻的有序子序列，直到最后只剩下 1 个有序的序列。

现给定原始序列和由某排序算法产生的中间序列，请你判断该算法究竟是哪种排序算法？

输入格式：

输入在第一行给出正整数 n (≤100)；随后一行给出原始序列的 n 个整数；最后一行给出由某排序算法产生的中间序列。这里假设排序的目标序列是升序。数字间以空格分隔。

输出格式：

首先在第 1 行中输出Insertion Sort表示插入排序、或Merge Sort表示归并排序；然后在第 2 行中输出用该排序算法再迭代一轮的结果序列。题目保证每组测试的结果是唯一的。数字间以空格分隔，且行首尾不得有多余空格。

输入样例 1：

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

输出样例 1：

Insertion Sort
1 2 3 5 7 8 9 4 6 0

输入样例 2：

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

输出样例 2：

Merge Sort
1 2 3 8 4 5 7 9 0 6

解析

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> origin(n), mid(n), tmp(n);

    for (int i = 0; i < n; i++) cin >> origin[i];
    for (int i = 0; i < n; i++) cin >> mid[i];

    // ----- 判断是否为插入排序 -----
    tmp = origin;
    bool isInsertion = false;

    for (int i = 1; i < n; i++) {
        int key = tmp[i];
        int j = i - 1;
        while (j >= 0 && tmp[j] > key) {
            tmp[j + 1] = tmp[j];
            j--;
        }
        tmp[j + 1] = key;

        if (tmp == mid) {         // 发现中间序列
            isInsertion = true;
            // 继续插入下一轮
            i++; // 下一轮 i++
            if (i < n) {
                key = tmp[i];
                j = i - 1;
                while (j >= 0 && tmp[j] > key) {
                    tmp[j + 1] = tmp[j];
                    j--;
                }
                tmp[j + 1] = key;
            }
            cout << "Insertion Sort\n";
            for (int k = 0; k < n; k++) {
                if (k) cout << " ";
                cout << tmp[k];
            }
            return 0;
        }
    }

    // ----- 否则是归并排序 -----
    cout << "Merge Sort\n";

    tmp = origin;
    bool flag = false;

    for (int step = 1; step < n; step *= 2) {
        vector<int> last = tmp;

        for (int i = 0; i < n; i += 2 * step) {
            int l = i;
            int midPos = min(i + step, n);
            int r = min(i + 2 * step, n);
            inplace_merge(tmp.begin() + l, tmp.begin() + midPos, tmp.begin() + r);
        }

        if (flag) {   // 上一步就是输入的中间序列 → 输出下一轮
            for (int k = 0; k < n; k++) {
                if (k) cout << " ";
                cout << tmp[k];
            }
            return 0;
        }

        if (tmp == mid) flag = true;  // 找到匹配的中间步骤
    }

    return 0;
}