在P1217的题解中篇发布前先来插播一个题目，难度不大所以可以放心食用。

先来回顾原题： 

题目描述

输入n(1 <= n < 5000000 且n为奇数)个数字a_i(1<=a_i<10^9)，输出这些数字的第k小的数。最小的数是第 0 小。

请尽量不要使用nth_element来写本题，因为本题的重点在于练习分治算法。

输入格式

第一行有两个整数，分别表示n和k。

第二行有n个整数，第i个数表示a_i。

输出格式

一个整数，表示第k小的数。

题目并不难，我们最简单粗暴的办法就是写一个快排，然后直接输出有序数组的第k个值。 

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e6+10;
void quick_sort(int a[],int l,int r)
{
    if(l>=r) return;
    int i=l-1,j=r+1,x=a[l+r>>1];
    while(i<j)
    {
        do i++;while (a[i]<x);
        do j--;while (a[j]>x);
        if(i<j) swap(a[i],a[j]);
    }
    quick_sort(a,l,j),quick_sort(a,j+1,r);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n,k;
    cin>>n>>k;
    int a[maxn];
    for(int j=0;j<n;j++)
    {
        cin>>a[j];
    }
    quick_sort(a,0,n-1);
    cout<<a[k];
    return 0;

}

所以你兴冲冲地写完了代码，正打算开始编译运行，没想到编译器抛出异常Segmentation fault。

这下懵了，对于一个刚刚入门的OIer来说这种异常很是罕见，于是聪明的你马上打开浏览器问起了deepseek。得到了以下回答： 

栈空间溢出 (Stack Overflow)
int a[maxn];  // maxn=5e6+10 = 5,000,010
在 main() 函数中声明这么大的数组会占用约 20MB 的栈空间
大多数系统的默认栈大小只有 8MB 左右
这会导致栈溢出，从而引发段错误

好好好，一直顺手的const int今天神奇的成了罪魁祸首，那么该怎么解决呢？虽然我们说C++是需要定义静态变量来申请内存空间的，但是不代表没有动态的数据类型啊！在指导下，你甩出了： 

int* a = new int[n];

这行代码很好理解，定义数组a，其空间大小由n决定。但是我还是想好好讲讲这样写的特点在哪里：

1.常规的int方法对定义的数组规模是固定的，在编译时确定。而new方法在运行时确定。

2.int方法得到的是一个栈上的“实体”数组，其元素紧邻，在释放的时候更有栈的递归特性，所以访问速度快效率高，但是缺点也很明显，就是固定。而new方法实际上得到的是一个内存指针，定义得到的实际上是指向动态分配的内存空间的起始地址。通过将多个不一定连续的内存空间用指针的形式链接成数组，访问效率相对较低，但是灵活性好。

3.静态数组会在作用域结束的时候自动释放内存，动态分配的数组则需要手动释放内存（因为其不连续性）。并且，当内存不足时，new方法由于没有足够的内存空间，会抛出一个std::bad_alloc异常。

不过别忘了，申请了动态内存，也要有随手释放空间的习惯，避免出现内存被占用。所以在最后记得写上： 

delete[] a;

至此，代码正常运行，你也很顺利的ac了。不过ac的时候，这个异常也引起了你的兴趣，于是你认真观察了几个数据点：

好家伙，第五个数据点竟然占据了足足19.66MB的内存空间，难怪要抛出异常！