题目描述
编写用两个 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;
}
说实话，不知道你写的什么，但是有一点就是非常啰嗦。要是明天有空的话就写一个给你参考参考。
```c
#define LEN 17 //最后一个结束符要加上1个字节
typedef struct ScoreNode
{
int score;
char name[LEN];
struct ScoreNode *prev;
struct ScoreNode *next;
} ScoreNode;
int main()
{
int f, i, n, l;
ScoreNode *psnadd, *psntravel, *psnMid, *psnLast;
ScoreNode **ppsnMid;
scanf("%d", &n);
if(n<1 || n>10000)
{
return 1; //题目中如果有错误代码，那就按题目要求来。
}
f = 1;
i = 0;
l = 0;
psnLast = (ScoreNode *)malloc(sizeof(ScoreNode)); //此节点放在链表末尾不储存学生信息
psnLast->score = 1000001;
psnLast->prev = psnLast;
psnLast->next = psnLast;
psnMid = psnLast;
ppsnMidList = (ScoreNode **)malloc(sizeof(ScoreNode *)*(n + (n>>1)));
while(i < n)
{
psnadd = (ScoreNode *)malloc(sizeof(ScoreNode));
scanf("%d %s", &psnadd->score, psnadd->name); //成绩和名字自己考虑是否需要验证准确性
if(psnadd->score < psnMid->score)
{
f--;
psntravel = psnLast->next;
}
else
{
f++;
psntravel = psnMid;
}
while(psnadd->score > psntravel->score)
{
psntravel = psntravel->next;
}
psnadd->prev = psntravel->prev;
psnadd->prev->next = psnadd;
psnadd->next = psntravel;
psntravel->prev = psnadd;
if(f == 0)
{
psnMid = psnMid->prev;
}
else if(f == 1)
{
psnMid = psnMid->next;
}
i++;
f = i & 1;
ppsnMidList[l++] = psnMid;
if(f == 0)
{
ppsnMidList[l++] = psnMid->next;
}
}
i = l - f;
l = 0;
while(l < i)
{
printf("%d %s/n%d %s %d %s/n", ppsnMidList[l]->score, ppsnMidList[l]->name, ppsnMidList[l+1]->score, ppsnMidList[l+1]->name, ppsnMidList[l+2]->score, ppsnMidList[l+2]->name);
l = l + 3;
}
if(f == 1)
{
printf("%d %s/n", ppsnMidList[l]->score, ppsnMidList[l]->name);
}
psntravel = psnLast->prev;
for(; ; )
{
free(psntravel->next);
if(psntravel->prev == psnLast)
{
break;
}
psntravel = psntravel->prev;
}
free(psntravel);
free(ppsnMidList);
return 0;
}
```