题目描述
编写用两个 Heap 实现动态查找中位数的程序
你最终编写的程序的整体复杂度应该低于 Θ(n^2)，否则可能会因为超时无法通过评测系统中的全部测试
现有 n 个学生的成绩和姓名，每当输入一个学生的信息，你需要计算学生成绩的中位数，并输出位于中间的学生的成绩和姓名
输入格式
第一行为 n，表示接下来有 n 行，每行描述了一个学生的成绩和姓名，其格式如下：
<成绩> <姓名> 表示一个学生的成绩和他的姓名，<成绩>和<姓名>之间有一个空格
<姓名> 由 1 到 16 个大小写字母组成，<成绩> 为 0 到 1000000 的整数
测试数据中不会含有<成绩>相同的数据，从而中位数是唯一的
测试数据中可能含有<姓名>相同的数据，可视为碰巧重名的不同学生，你在编程的时候不需要特殊考虑姓名是否相同的问题
输出格式
需要输出 n 行，每读入一条数据就可以输出一行
在第 m 行中输出时只需要考察（按输入顺序）前 m 个学生，输出它们之中成绩位于中间的学生的成绩和姓名。
当 m 为奇数时，中位数唯一，是成绩在第 (m+1)/2 的学生，输出格式为：
<成绩> <姓名>
当 m 为偶数时，中位数有两个，分别是成绩在第 m/2 的学生和成绩在第 m/2+1 的学生，输出格式为（先输出成绩低的，后输出成绩高的，即<成绩1><<成绩2>）：
<成绩1> <姓名1> <成绩2> <姓名2>
同一行的<成绩>和<姓名>之间有一个空格
例如：在第 5 行输出的是前 5 个学生中成绩排第 3 的学生的成绩和姓名；在第 6 行输出的是前 6 个学生中成绩排第 3 的和成绩排第 4 的学生的成绩和姓名
输入范例
8
148 GHuMEAyLnLFDxFI
1 Alexstrasza
573 ScXGgbWkFNQdU
529 NFoZVsrTKj
100 Alexstrasza
884 pGgXrpNrvY
61 wCYSYyCQP
1000 Alexstrasza
输出范例
148 GHuMEAyLnLFDxFI
1 Alexstrasza 148 GHuMEAyLnLFDxFI
148 GHuMEAyLnLFDxFI
148 GHuMEAyLnLFDxFI 529 NFoZVsrTKj
148 GHuMEAyLnLFDxFI
148 GHuMEAyLnLFDxFI 529 NFoZVsrTKj
148 GHuMEAyLnLFDxFI
148 GHuMEAyLnLFDxFI 529 NFoZVsrTKj
数据规模
n <= 10000
我写的代码：
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#define LEN 16
struct Node
{
int score;
char name[LEN];
};
void up(struct Node*T, int n,int i)
{
int k = i;
int val = T[i].score;
int L, j=-1;
char temp[LEN];
strcpy(temp,T[i].name);
while(j!=k)
{
j = k;
if(j>0&&T[(j-1)/2].score<val)
{
k=(j-1)/2;
T[j].score=T[k].score;
strcpy(T[j].name,T[k].name);
}
}
if (k != i)
{
T[k].score = val;
strcpy(T[k].name,temp);
}
}
void reup(struct Node*T, int n,int i)
{
int k = i;
int val = T[i].score;
int L, j=-1;
char temp[LEN];
strcpy(temp,T[i].name);
while(j!=k)
{
j = k;
if(j>0&&T[(j-1)/2].score>val)
{
k=(j-1)/2;
T[j].score=T[k].score;
strcpy(T[j].name,T[k].name);
}
}
if (k != i)
{
T[k].score = val;
strcpy(T[k].name,temp);
}
}
void sift(struct Node*T, int n, int i)
{
int k = i;
int val = T[i].score;
int L, j=-1;
char temp[LEN];
strcpy(temp,T[i].name);
while(j!=k)
{
j = k;
if (2 * j + 1 < n)
{
L = 1;
if (2 * j + 2 <n && T[2 * j + 2].score > T[2 * j + 1].score)
{
L = 2;
}
if (T[2 * j + L].score > val)
{
T[k].score = T[2 * j + L].score;
strcpy(T[k].name,T[2 * j + L].name);
k = 2 * j + L;
}
}
}
if (k != i)
{
T[k].score = val;
strcpy(T[k].name,temp);
}
}
void resift(struct Node*T, int n, int i)
{
int k = i;
int val = T[i].score;
int L, j=-1;
char temp[LEN];
strcpy(temp,T[i].name);
while(j!=k)
{
j = k;
if (2 * j + 1 < n)
{
L = 1;
if (2 * j + 2 <n && T[2 * j + 2].score <T[2 * j + 1].score)
{
L = 2;
}
if (T[2 * j + L].score<val)
{
T[k].score = T[2 * j + L].score;
strcpy(T[k].name,T[2 * j + L].name);
k = 2 * j + L;
}
}
}
if (k != i)
{
T[k].score = val;
strcpy(T[k].name,temp);
}
}
int main()
{
int n;
scanf("%d",&n);
struct Node*minT;
struct Node*maxT;
minT=(struct Node*)malloc(sizeof(struct Node)*10000);
maxT=(struct Node*)malloc(sizeof(struct Node)*10000);
int score;
char name[LEN];
for(int i=0;i<n;i++)
{
scanf("%d %s",&score,&name);
if(i==0)
{
maxT[0].score=score;
strcpy(maxT[0].name,name);
printf("%d %s\n",maxT[0].score,maxT[0].name);
}
else if(i==1)
{
if(score>maxT[0].score)
{
minT[0].score=maxT[0].score;
strcpy(minT[0].name,maxT[0].name);
maxT[0].score=score;
strcpy(maxT[0].name,name);
}
else
{
minT[0].score=score;
strcpy(minT[0].name,name);
}
printf("%d %s %d %s\n",minT[0].score,minT[0].name,maxT[0].score,maxT[0].name);
}
else
{
if(i%2==0)
{
if(score>minT[0].score)
{
maxT[i/2].score=score;
strcpy(maxT[i/2].name,name);
reup(maxT,i/2+1,i/2);
}
else
{
maxT[i/2].score=minT[0].score;
strcpy(maxT[i/2].name,minT[0].name);
reup(maxT,i/2+1,i/2);
minT[0].score=score;
strcpy(minT[0].name,name);
sift(minT,i/2,0);
}
printf("%d %s\n",maxT[0].score,maxT[0].name);
}
else
{
if(score>maxT[0].score)
{
minT[i/2].score=maxT[0].score;
strcpy(minT[i/2].name,maxT[0].name);
up(minT,i/2+1,i/2);
maxT[0].score=score;
strcpy(maxT[0].name,name);
resift(maxT,i/2+1,0);
}
else
{
minT[i/2].score=score;
strcpy(minT[i/2].name,name);
up(minT,i/2+1,i/2);
}
printf("%d %s %d %s\n",minT[0].score,minT[0].name,maxT[0].score,maxT[0].name);
}
}
}
return 0;
}
