注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

东月之神

在单纯的观念里面,生命就容易变得比较深刻!

 
 
 

日志

 
 
关于我

别驻足,梦想要不停追逐,别认输,熬过黑暗才有日出,要记住,成功就在下一步,路很苦,汗水是最美的书!

网易考拉推荐

Running Median  

2010-05-23 12:31:51|  分类: ACM |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
Problem Description
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.
 

Input
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.
 

Output
For each data set the first line of output contains the data set number, a single space and the number of medians output (which should be one-half the number of input values plus one). The output medians will be on the following lines, 10 per line separated by a single space. The last line may have less than 10 elements, but at least 1 element. There should be no blank lines in the output.
 

Sample Input
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
 

Sample Output
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
 
题目意思就是求中位数,输入为奇数的时候输出已经输入的数中的中位数。一开始用了向量vector+插入排序,超慢,于是用了二分插入,好了很多,听说能用树状数组做,后来写了,确实很快。下面是三个搓搓的代码:
1:
 #include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
int main()
{
 vector<int> v, s;
 int n, i, a, t, j, b;
 cin >> t;
 while(t--)
 {
    cin  >> a >> n;
    {
  vector<int>::iterator it;
  scanf("%d", &b);
    v.push_back(b);
        s.push_back(b);
        int p = 0;
        for(i = 0; i < (n-1) / 2; i++)
  {
              for(j = 0; j < 2; j++)
              {
    int k;
    scanf("%d", &b);
    int flag = 1;
    for(it = v.begin(), k = 0; it != v.end() && flag; it++, k++)
    {
        if(b >= *it)
        {
            v.insert(v.begin()+k, b);
            flag = 0;
        }
                }
                if(flag)
        v.push_back(b);
        }
            s.push_back(v[v.size()/2]);
  }
  printf("%d %d\n", a, (n+1)/2);
  int k;
     for(it = s.begin(), k = 1; it != s.end(); it++, k++)
     {
            printf("%d ", *it);
        if(k % 10 == 0)
            printf("\n");
        }
        printf("\n");
     v.clear();
     s.clear();
       }
    }
return 0;
}
2:
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
 
int main()
{
 int n, i, a, j, t, ii, jj;
 while(scanf("%d", &t) != EOF)
 {
 while(t--)
 {
     vector<int> v;
  scanf("%d%d", &ii, &n);
  printf("%d %d\n", ii, n/2+1);
  jj = 1;
  scanf("%d", &a);
  v.push_back(a);
  printf("%d ", a);
  for(i = 1; i < n; i+=2)
  {
   for(j = 0; j < 2; j++)
   {
    cin >> a;
    int left = 0, right = i+j, mid;
    while(left <= right)
    {
     mid = (right + left) >> 1;
     if(v[mid] >= a) right = mid-1;
     else  left = mid+1;
    }
    if(left > i+j) left = i+j;
    v.insert(v.begin()+left, a);
   }
   printf("%d ", v[v.size()/2]);
   ++jj;
   if(jj % 10 == 0) printf("\n");
  }
  if(jj %10 != 0)
   printf("\n");
  v.clear();
 }
 }
return 0;
}
 
3:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 10000;
int c[maxn], a[maxn], m, s[maxn];
inline int lowbit(int x)
{
 return x & (-x);
}
inline void update(int x, int d)
{
 while(x <= m)
 {
  c[x] += d;
  x += lowbit(x);
 }
}
inline int getsum(int x)
{
 int sum = 0;
 while(x > 0)
 {
  sum += c[x];
  x -= lowbit(x);
 }
return sum;
}
inline int find(int x)
{
 int l = 1, r = m, mid;
 while(l <= r)
 {
  mid = (l + r) >> 1;
  if(a[mid] == x)  return mid;
  if(a[mid] >= x)  r = mid-1;
  else l = mid + 1;
 }
}
inline int search(int num)
{
    int l = 1, r = m;
    while(l <= r)
    {
        int mid = (l + r) / 2;
        if(getsum(mid) >= num) r = mid - 1;
        else l = mid + 1;
    }
return l;
}
int main()
{
 int n, i, j, ans, cnt, t, ii;
 scanf("%d", &t);
 while(t--)
 {
  scanf("%d%d", &ii, &n);  
  memset(c, 0, sizeof(c));
  for(j = 1, i = 1; i <= n; i++)
  {
   scanf("%d", &s[i]);
   a[j++] = s[i];
  }
  sort(a+1, a+n+1);
  for(m = 1, i = 2; i <= n; i++)
   if(a[i] != a[i-1])
    a[++m] = a[i];
  printf("%d %d\n", ii, (n+1) / 2);
  cnt = 0;
  for(i = 1; i <= n; i++)
  {
   ans = find(s[i]);
   update(ans, 1);
   if(i % 2 == 1)
   {
    ans = search((i+1)/2);
    printf("%d", a[ans]);
    ++cnt;
    if(cnt % 10 == 0)printf("\n");
    else if(i != n) printf(" ");
   }   
  }
  if(cnt % 10 != 0) printf("\n"); 
 }
return 0;
}
 
  评论这张
 
阅读(380)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017