四分位数间距：是上四分位数与下四分位数之差,用四分位数间距可反映变异程度的大小.
即：Q3 --Q1
四分位数求法

第一步

　　确定四分位数的位置
四分位数是将数列等分成四个部分的数，一个数列有三个四分位数，设下四分位数、中位数和上四分位数分别为Q1、Q2、Q3，则：Q1、Q2、Q3的位置可由下述公式确定：
Q1的位置 (n+1)/4
Q2的位置 (n+1) /2
Q3的位置 3(n+1)/4
式中n表示资料的项数
第二步

　　根据第一步所确定的四分位数的位置，确定其相应的四分位数。
例1

　　例如：某车间某月份的工人生产某产品的数量分别为13、13.5、13.8、13.9、14、14.6、14.8、15、15.2、15.4、15.7公斤，则三个四分位数的位置分别为：
Q1的位置 (n+1)/4 =(11+1)/4=3
Q2的位置 (n+1) /2=(11+1)/2=6
Q3的位置 3(n+1)/4=3(11+1)/4=9
即变量数列中的第三个、第六个、第九个工人的某种产品产量分别为下四分位数、中位数和上四分位数。即：
Q1 = 13.8公斤、Q2 = 14.6公斤、Q3 = 15.2公斤

本文作者：vxbomath
大家好，今天讲解高中数学数列通项的 11 种方法其中三个方法：累加法、 累乘法、 待定系数法。下面跟随我一起来来看看。
一接下来我们就开始数列解题——累加法
二、接下来我们就开始数列解题——累乘法
三、接下来我们就开始数列解题——待定系数法
好了，今天就分享到这里。更多高中数学解题技巧在体系课里或者需要听公开直播免费课程有需要请私信老师。

基本方法就是数学分析：设p(i)表示i-1节点向i节点要糖果的数量（有符号，表示方向），avg表示糖果数的均值，也就是目标糖果数，设p（1）=k 也就是节点n向节点1要的糖果数。则存在以下公式：
p(2)=p(1)+avg-a[1]
p(3)=p(2)+avg-a[2]=(2*avg)-(a[1]+a[2])-k;
p(i)=p(i-1)+avg-a[i-1]=(i-1)*avg-(a[1]+......+a[i-1])-k;
题目的最优解就是p1+……pn绝对值的最小值，设S(i)表示a[1]+……+a[i]-avg*(i)。
则p(i)=k-S(i-1)  p(1)可看做k-S(n)
所以当k是S(1)到S(n)的中位数时，合最小
#include <iostream>
#include <algorithm>

using namespace std;

long long data[1000005];
long long total[1000005];

int main()
{
	int n;
	while(cin>>n)
	{
		for(int i=0;i<n;i++)
		{
			cin>>data[i];
			if(i>0)
				total[i]=total[i-1]+data[i];
			else total[i]=data[i];
		}
		long long avg=total[n-1]/n;
		for(int i=0;i<n;i++)
			total[i]=abs(total[i]-(i+1)*avg);
		sort(total,total+n);
		long long mid=abs(total[n/2]);
		long long result=0;
		for(int i=0;i<n;i++)
		{
			result+=abs(total[i]-mid);
		}
		cout<<result<<endl;
	}
}

时间不够代码没写注释，抱歉!!!
题目（1）
时间限制: 400 ms  内存限制: 64 MB   代码长度限制: 16 KB


简单分析
简单来说就是求  N的k次方mod素数10007    这里用到两个公式。

费马小定理：和 基本定律  (a + b * n) mod n ≡ a mod n

详细可以看：https://www.zybuluo.com/Lin--/note/1373807 上面有简单描述。
代码
int Power(int a, int b)
{
    if(a > 10007 || b > 10006)
        return Power(a%10007, b%10006);
    if(a == 0)
        return 0;
    int answer = 1, tmp = 0;
    while(tmp < b)
    {
        answer *= a;
        if(answer >= 10007)
            answer = answer % 10007;
        tmp++;
    }
    return answer;
}

题目(2)
时间限制: 1200 ms  内存限制: 24 MB  代码长度限制: 16 KB




简单分析
与两个等长有序序列的中位数类似（折半查找和merge算法）

merge算法(伪代码)：
输入：数组A[1...m]和它的三个索引去p,q,r，1 <= p <= q < r <= m,两个子数组A[p...q]和A[q+1...r]各自按升序排列
输出:合并两个子数组A[p...q]和A[q+1...r]

comment: B[p...r]是个辅助数组
s <- p; t <- q + 1; k <- p
while s <= q and t <= r
	if A[s] <= A[t] then
		B[k] <- A[s]
		s <- s + 1
	else
		B[k] <- A[t]
		t <- t + 1
	end if
		k <- k + 1
end while
if s = q + 1 then B[k...r] <- A[t...r]
else B[k...r] <- A[s...q]
end if
A[p...r] <- B[p...r]

merge算法因为是得到一个新的排序所以复杂度为Θ（n），但是我们不用那么多信息，所以我们不需要一个个的往后比较，使用二分的方法可以将时间复杂度降为Θ（log2n）。

find_midian 的算法
输入:数组A[1...n]和B[1...n]
输出:两个子数组的合并数组的中位数p
s <- 1; q <- 1; k <- m - 1
while m > 1
	if A[s + (k + 1)/2] > B[q + (k + 1)/2]) then
		s <- s + (k + 1)/2
	else
		q <- q + (k + 1)/2
	end if
	k <- k/2
end while
if A[s] < B[s]（这里输出低位中位数） then
	p <- A[s]
else
	p <- B[s]

上面是等长数组的，而非等长数组我们则需要将其删减为等长数组。A[1…n]和B[1…m]两个数组，假设n > m + 1，则数组A中存在不可能是中位数的位置。

如：若n > m + 1的情况下，即使在最极端的A[n] > B[1]的情况下，A[(m+n)/2…n]是无法被选取为中位数的，即使同理，A[1] < B[m]的情况下，A[1…(m - n)/2]也是无法被取为中位数的。
Array (A[1], A[2], ... , A[m], B[1], ... , B[n])的中位数为 A[(m+n)/2]
Array ( B[1], ... , B[n] , A[1], A[2], ... , A[m])的中位数为 A[(m-n)/2]

但是这里我们把数组A删除至长度为 M + 1 ，A数组可以被选为中位数的长度段为 A [ (m - n - 1) / 2 … (m + n) / 2 ]，我们仍然需要讨论特例A[(m + n) / 2]，若A[(m + n) / 2] < B[0] 时，中位数就是A[(m + n) / 2]啦，如果还没找到剩下的两个数组丢到上面的find_midian里面运算完就是中位数啦
代码
int median(int *a,int *b, int n1,int n2,int lowa,int lowb)
{
    if(n1 > n2)
    {
        lowa = (n1 - n2 - 1)/2;
        if(a[lowa + n2] < b[0])
            return a[lowa + n2];
        if(a[lowa] > b[n2 - 1])
            return a[lowa];
    }
    if(n1 < n2)
    {
        lowb  = (n2 - n1 - 1)/2;
        if(b[lowb + n1] < a[0])
            return b[lowb + n1];
        if(b[lowb] > a[n1 - 1])
            return b[lowb];
    }
    int shanchu;
    if(n2 > n1)
        shanchu = n1;
    else
        shanchu = n2;
    int tmp_shan = 0;
    while(shanchu != 0)
    {
        tmp_shan = (shanchu + 1)/2;
        if(a[lowa + tmp_shan - 1] > b[lowb + tmp_shan - 1])
            lowb += tmp_shan;
        else
            lowa += tmp_shan;
        shanchu -= tmp_shan;
    }
    if(a[lowa] < b[lowb])
        return a[lowa];
    else
        return b[lowb];
}

备注
如果这里没有懂，请麻烦私聊我，之后我尽量改进自己的描述
题目（3）
时间限制: 10000 ms 内存限制: 64 MB 代码长度限制: 16 KB


分析
简单的排序，10000的随机正整数，用Θ（nlog2n）的任意算法都行吧。

这里用的是快排，写的不是很好。
代码
#include <iostream>
using namespace std;
void quick_sort(int a[], int length)
{
    if(length < 2)
        return;
    int side = 0, tmp;
    for(int num = 1; num < length; num++)
    {
        if(a[num] > a[0])
        {
            side++;
            tmp = a[side];
            a[side] = a[num];
            a[num] = tmp;
        }
    }
    tmp = a[side];
    a[side] = a[0];
    a[0] = tmp;
    quick_sort(a,side);
    quick_sort(a+side+1,length-side-1);
}
int arr[1000000];
int main()
{
    std::ios::sync_with_stdio(false);
    int length;
    cin >> length;
    for(int num = 0; num < length; num++)
        cin >> arr[num];
    quick_sort(arr,length);
    for(int num = length - 1; num > 0; num--)
        cout << arr[num] << " ";
    cout << arr[0];
}

题目(4)
时间限制: 400 ms 内存限制: 64 MB 代码长度限制: 16 KB

提示把算法描述的很好了，我就瞎叨叨了。
代码
#include <iostream>
using namespace std;
int arr[1000];
int quick_sort(int arr[], int length, int k)
{
    if(length == 1)
        return arr[0];
    int side = 0, side2 = 0, tmp;
    for(int num = 1; num < length; num++)
    {
        if(arr[num] == arr[0])
            side2++;
        if(arr[num] < arr[0])
        {
            side++;
            tmp = arr[num];
            arr[num] = arr[side];
            arr[side] = tmp;
        }
    }
    if(side > k - 1 && side > 0)
        return quick_sort(arr + 1, side, k);
    else if(side + side2 < k - 1 && side + side2 > 0)
        return quick_sort(arr + side + 1, length - side - 1, k - side - 1);
    else
        return arr[0];
}
int main()
{
    std::ios::sync_with_stdio(false);
    int length, k;
    cin >> length;
    cin >> k;
    for(int tmp = 0; tmp < length; tmp++)
        cin >> arr[tmp];
    cout << quick_sort(arr,length,k);
}