DS：实验室的仓库中有n堆的财宝，第i堆财宝有a[i]个

题目描述

实验室的仓库中有n堆的财宝，第i堆财宝有a[i]个，且价值均为i。面对如此多的财宝，实验室的管理员每天都会来统计这些财宝的中位数是什么。 但是每天实验室都会有开销，每天的开销为第k大的财宝，聪明的你能帮助管理员统计每天结束后的财宝吗？

输入格式

第一行为一个n，表示有n堆财宝。 第二行有n个数，a[i]表示第i堆财宝的数量。 第三行为一个q，表示一共有q天。 而后一共q行，每行一个k，表示每一天的开销为剩余财宝的第k大的财宝。

输出格式

一共输出q行，表示第i天后财宝的中位数。结果保留1位小数。

输入输出样例

输入

输入示例

---

 

5

1 2 1 2 1

2

2

1

 

---

输出示例

---

2.5

2.0

 题意分析：

      举示例分析，有5堆财宝，第一堆只有1个，这个价值为1，第二堆有两个，每个的价值为2，第三堆只有1个，该财宝价值为3，第四堆有2个，每个价值为4，第五堆只有一个，价值为5；

按价值升序排序得：1，2，2，3，4，4，5

去掉第2大的后为：1，2，2，3，4，5，中位数为：2.5

再去掉第一大的后为：1，2，2，3，4，中位数为：2.0

所以思路就是将价值升序的序列用数组表示

然后删除数组中的元素，如果最后数组长度为奇数，则中位数为数组中间的值，否则为中间两数的平均值

完整代码：

#include
#include
using namespace std;
//const int N = 10001000;
int a[1000000],real[1000000];//大数组要定义在函数外面，否则会出现堆栈溢出的问题
void delete1(int *a,int x,int n)	//删除长度为n数组中第x大的元素
{
	for(int i = n - x;i < n - 1;i ++)
	{
		a[i] = a[i + 1];
	}
}
int main()
{
	int n,q,b[1000],k = 0;
	cin >> n;
	for(int i = 0;i < n;i ++)
	{
		cin >> a[i];
	}
	cin >> q;
	for(int i = 0;i < q;i ++)
	{
		cin >> b[i];
	}
	for(int i = 0;i < n;i ++)
	{
		while(a[i] --)
		{
			real[k] = i + 1;//real为价值的升序数组
			k ++;
		}
	}
	double c[1000];
	int j = 0;
	for(int i = 0;i < q;i ++)
	{
		delete1(real,b[i],k);
		k --;
		if(k % 2 != 0)
		{
			c[j] = real[k / 2];
			j ++;
		}
		else
		{
			c[j] = (real[k / 2] + real[(k / 2) - 1]) * 1.0 / 2;
			j ++;
		}
	}
	for(int i = 0;i < q - 1;i ++)
	{
		cout << fixed << setprecision(1) << c[i] << endl;
	}
	cout << fixed << setprecision(1) << c[q - 1];
	return 0;
}