Question

急！求大牛解决一道简单的acm题！！！非常感谢！！

Input
多组测试数据 对于每组测试数据： 第1行： 一个整数N（1 <= N <= 100,000），表示ACMaryland将会进行的操作次数 第2..N+1行： 每一行表示一次操作（第一次操作肯定是1类型）： 1、如果输入两个整数，1 X，接收某个传感器返回的坐标值X； 2、如果输入一个整数，2，根据当前已收集的坐标值，计算并输出世界中心；

Output
如果当前操作输入为一个整数2，则打印输出当前世界中心，注意输出统一保留小数点后一位。 输入的最后是0，表示输入结束，这组数据不用处理。

Sample Input

8
1 2
1 3
2
1 4
2
2
1 -4
2

Sample Output

2.5
3.0
3.0
2.5

Hint
Sample 说明 首先输入两个数2,3，此时序列为{2, 3}，输入操作2，根据定义，可得中心为(2+3)/2 = 2.5，打印输出2.5；然后输入坐标4，序列更新为{2,3,4}，根据定义，可得中位数为3.0，根据输入的操作，则连续输出两个3.0；最后，输入坐标-4，根据定义，可得中位数为(2+3)/2 = 2.5，输出2.5。 中位数的定义： 对于一个含有m个元素的序列： 如果m为偶数，则中位数为第m/2个元素和第m/2+1个元素的平均值； 如果m为奇数，则中位数为第(m+1)/2个元素的值。

#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;
void zws(int n,int a[])
{ double x,y;
x=a[n/2-1]+a[n/2])/2;
y=a[(n+1)/2];
if(n%2==0)
printf("%.1f",x);
else
printf("%.1f",y);
}
int main()
{
int n;
while(scanf("%d",n)&&n<10000&&n>=1)
{
int i,m,a[10000];
for(i=0;i<n;i++)
{scanf("%d%d",m,a[i]);
if(m==2)
zws(i,a[i]);

}
}
}

我的程序错在哪里了啊？

Answer 1

要排序 否则你的中位数就是错的

#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;
int a[100001];
int main()
{
int n,m;
while(scanf("%d",&n)!=EOF)
{
int i,j,x,t;
m = 0;
for(i=0;i<n;i++)
{
scanf("%d",&x);
if(x == 1){
scanf("%d",&t);
for(j = m-1;j>=0;j--)
if(a[j]>t)
a[j+1] = a[j];
else break;
a[j+1] = t;
m ++;
}
else if(x == 2){
if(m%2)printf("%.1lf\n",a[m/2]*1.0);
else printf("%.1lf\n",(a[m/2]+a[m/2-1])/2.0);
}
}
}
return 0;
}

追问

嗯，确实是要排序，我理解错了，以为中位数就是中间位置的数呢……
你的程序是正确的，可是超时了……“Time Limit Exceed ，3080ms， 532kb， G++ ，529B ~”
怎么办？

追答

这道题目并不简单，需要足够的算法优化能力，如果你还只是初步学习的话就可以先看看
想了一个晚上，给你优化了一个可行的代码，不过效果也没有你学学校oj上其他运行时间快
300多ms，采用的是链表排序，时间复杂度n^1.5
效果可见：http://acm.scs.bupt.cn/onlinejudge/newoj/Statistic/Statistic.php?problem_id=67的账号nicktest

#include
#include
using namespace std;
#define M 350
#define N 100001
struct Node{
int v;
Node *prev,*next;
}node[N];
Node *inde[M],*mid,*last,*start;
void insert(Node *add,int lm,int m)
{
if(last == NULL){
start = last = mid = add;
return;
}
if(last->v v){
last->next = add;
add->prev = last;
last = add;
}
else if(start->v > add->v){
add->next = start;
start->prev = add;
start = add;
for(int i = lm-1;i >= 0;i --)inde[i] = inde[i]->prev;
}
else{
int i = lm-1;
while(i>=0 && inde[i]->v>add->v){
inde[i] = inde[i]->prev;
i --;
}
Node *p;
if(i == lm-1)p=last->prev;
else{
p=inde[i+1];
if(p->vv)inde[i+1]=add;
}
while(p->v>add->v)p=p->prev;
add->prev = p;
add->next = p->next;
p->next->prev = add;
p->next = add;
}
if(mid->vv){
if(m%2)mid=mid->next;
}
else{
if(m%2==0)mid=mid->prev;
}
}
int main()
{
int n,m,lm;
while(scanf("%d",&n)!=EOF)
{
int i,x,tt;
m = 0;
lm = 0;
start=mid=last=NULL;
for(i=0;iv = tt;
add->next=add->prev=NULL;
insert(add,lm,m);
if(m%M == 0)
inde[lm++]=last;
}
else if(x == 2){
double ans = mid->v;
if(m%2==0)ans=(ans+mid->next->v)/2.0;
printf("%.1lf\n",ans);
}
}
}
return 0;
}