归并排序(merge sort)
组别：提高级
难度：5
归并排序是基于分治算法的一种排序，我们把一个问题分解成子问题，每个子问题再分别解决，最后再把子问题的解合并成最终结果。
如下图数列{6,5,12,10,9,1}，首先将数列分成两分{6,5,12}和{10,9,1}，再把这俩个子数列继续分解成{6},{5,12},{10},{9,1} ，当就子数列就剩两个元素时比较大小，现把子数列逐级合并成一个有序数列。
代码实现：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 | /**************************************************************** * Description: 用C++实现归并算法，Merge sort in C++ * Author: Alex Li * Date: 2022-02-10 19:55:32 * LastEditTime: 2023-11-11 21:58:28 ****************************************************************/ #include <iostream> using namespace std; int arr[100]; //定义主数组 int left_array[100],right_array[100];// 创建两个子数组Left_array和right_array // 合并两个子数组Left_arr和Right_arr到主数组里， void merge(int arr[], int left, int middle, int right) { //把arr数组分以middle为边界，别给到左子数组left_sub和右子数组left_right for (int i = left; i <=middle; i++)left_array[i] = arr[i]; for (int j = middle+1; j <=right; j++)right_array[j] = arr[j]; //维护子数组和主数组的当前索引 int left_index=left, right_index=middle+1, merged_index=left; // 在Left和Right数组中挑选最大的元素放入到主数组中, while (left_index <= middle || right_index <= right) { if(right_index>right||left_index<=middle&&left_array[left_index]<right_array[right_index]){ arr[merged_index++]=left_array[left_index++]; } else arr[merged_index++]=right_array[right_index++]; } return ; } //把主数组元素分解成两个子元素，排序并合并子数组 void mergeSort(int arr[], int begin, int end) { if (begin < end) { //middle是把主数组分成两个子数组的点 int middle = begin + (end - begin) / 2; mergeSort(arr, begin, middle); mergeSort(arr, middle + 1, end); // 合并排好序的子数组，Merge the sorted subarrays merge(arr, begin, middle , end); } } // 打印排好序数组，Print the sorted array void printArray(int arr[], int size) { for (int i = 0; i < size; i++) cout << arr[i] << " "; cout << endl; } //主程序 int main() { int size; cout<<"please input number for array size: "; cin>>size; cout<<"please input "<<size<<" elements of array:"; for (int i = 0; i <size; i++)cin>>arr[i]; mergeSort(arr, 0, size - 1); cout << "Sorted array: \n"; printArray(arr, size); return 0; } |
瑞士轮 [NOIP2011 普及组] [P1309]
题目背景
在双人对决的竞技性比赛，如乒乓球、羽毛球、国际象棋中，最常见的赛制是淘汰赛和循环赛。前者的特点是比赛场数少，每场都紧张刺激，但偶然性较高。后者的特点是较为公平，偶然性较低，但比赛过程往往十分冗长。
本题中介绍的瑞士轮赛制，因最早使用于1895年在瑞士举办的国际象棋比赛而得名。它可以看作是淘汰赛与循环赛的折中，既保证了比赛的稳定性，又能使赛程不至于过长。
题目描述
2×N名编号为 1∼2N的选手共进行R 轮比赛。每轮比赛开始前，以及所有比赛结束后，都会按照总分从高到低对选手进行一次排名。选手的总分为第一轮开始前的初始分数加上已参加过的所有比赛的得分和。总分相同的，约定编号较小的选手排名靠前。
每轮比赛的对阵安排与该轮比赛开始前的排名有关：第11 名和第22 名、第 33 名和第 44名、……、第2K−12K−1名和第2K2K名、…… 、第2N−12N−1名和第2N2N名，各进行一场比赛。每场比赛胜者得11分，负者得 00分。也就是说除了首轮以外，其它轮比赛的安排均不能事先确定，而是要取决于选手在之前比赛中的表现。
现给定每个选手的初始分数及其实力值，试计算在R 轮比赛过后，排名第QQ 的选手编号是多少。我们假设选手的实力值两两不同，且每场比赛中实力值较高的总能获胜。
输入格式
第一行是三个正整数N,R,QN,R,Q,每两个数之间用一个空格隔开，表示有 2×N2×N名选手、RR 轮比赛，以及我们关心的名次 QQ。
第二行是2×N2×N 个非负整数s1,s2,…,s2Ns1,s2,…,s2N，每两个数之间用一个空格隔开，其中sisi表示编号为ii 的选手的初始分数。 第三行是2×N2×N 个正整数w1,w2,…,w2Nw1,w2,…,w2N，每两个数之间用一个空格隔开，其中 wiwi 表示编号为ii 的选手的实力值。
输出格式
一个整数，即RR 轮比赛结束后，排名第QQ 的选手的编号。
输入输出样例
输入 #1复制2 4 2 7 6 6 7 10 5 20 15
输出 #1复制1
说明/提示
【样例解释】
【数据范围】
对于30%30%的数据，1≤N≤1001≤N≤100；
对于50%50%的数据，1≤N≤10,0001≤N≤10,000；
对于100%100%的数据，1≤N≤100,000,1≤R≤50,1≤Q≤2N,0≤s1,s2,…,s2N≤108,1≤w1,w2,…,w2N≤1081≤N≤100,000,1≤R≤50,1≤Q≤2N,0≤s1,s2,…,s2N≤108,1≤w1,w2,…,w2N≤108。