首页 > ACM题库 > HDU-杭电 > HDU 3282-Running Median[解题报告]HOJ
2014
03-13

HDU 3282-Running Median[解题报告]HOJ

Running Median

问题描述 :

For this problem, you will write a program that reads in a sequence of 32-bit signed integers. After each odd-indexed value is read, output the median (middle value) of the elements received so far.

输入:

The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. The first line of each data set contains the data set number, followed by a space, followed by an odd decimal integer M, (1 ≤ M ≤ 9999), giving the total number of signed integers to be processed.
The remaining line(s) in the dataset consists of the values, 10 per line, separated by a single space.
The last line in the dataset may contain less than 10 values.

输出:

The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. The first line of each data set contains the data set number, followed by a space, followed by an odd decimal integer M, (1 ≤ M ≤ 9999), giving the total number of signed integers to be processed.
The remaining line(s) in the dataset consists of the values, 10 per line, separated by a single space.
The last line in the dataset may contain less than 10 values.

样例输入:

3
1 9
1 2 3 4 5 6 7 8 9
2 9
9 8 7 6 5 4 3 2 1
3 23
23 41 13 22 -3 24 -31 -11 -8 -7
3 5 103 211 -311 -45 -67 -73 -81 -99
-33 24 56

样例输出:

1 5
1 2 3 4 5
2 5
9 8 7 6 5
3 12
23 23 22 22 13 3 5 5 3 -3
-7 -3

刚开始我连题目都没读懂。。题意是,当每次读入数据到奇数位时,寻找中间值。
比如第三组数据前五个数23 41 13 22 -3。
首先第一个数是23,肯定输出23
然后输入41 13,那么排序后得13 23 41,中间值还是23.
再输入22 -3,排序后得-3 13 22 23 41,那么中间值是22
接下来的一次类推。
我是傻傻的排序,貌似跟刚学的插入排序差不多。
在网上看见有更简单的方法,做个链接http://hi.baidu.com/lywdx1129/blog/item/7a01e4edf9464ada2f2e21da.html

 

 

//hdu 3282 Running Median
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;

void run()
{
 int n,m;
 scanf("%d%d",&n,&m);
 int i,num[10001];
 int ans[10001]={0},
 int u=2;

 printf("%d %d/n",n,(m+1)/2);
 scanf("%d",&num[1]);
 ans[1]=num[1];
 for(i=2;i<=m;i++) 
 {
  int tmp,j,k;
  scanf("%d",&tmp);
  if(tmp<=num[1]) //比第一个小,则后面的往后移
  {
   for(k=i-1;k>=1;k--)
   {
    num[k+1]=num[k];
   }
   num[1]=tmp; 
  }
  else if(tmp>=num[i-1]) //比最后一个大
  {num[i]=tmp;}
  else 
  {
   bool f=false;
   for(j=i-1;j>=1;j--)
   {
    if(tmp>=num[j-1] && tmp<=num[j]) //找要插入的位置位置
    {
     f=true;
     int k;
     {
      for(k=i-1;k>=j;k--)
      {
       num[k+1]=num[k];
      }
      num[j]=tmp;
     }
    }
    if(f==true) break;
   }
  }
  if(i%2==1) //记录奇数位置
  {
   ans[u++]=num[(i+1)/2];
  } 
 }
 for(i=1;i<u;i++)
 {
  if(i%10==0 || i==u-1) printf("%d/n",ans[i]);
  else printf("%d ",ans[i]);
 }
}
int main()
{ 
 int total;
 cin>>total;
 for(int now=1;now<=total;now++)  run();

 return 0;
}

参考:http://blog.csdn.net/jsjdream/article/details/5256637