每日一题4月9
Running Median
https://ac.nowcoder.com/acm/problem/50940
题意:给你n个数,当数字个数为奇数时输出此时的中位数
思路:以第一个数作为mid值,建立一个大顶堆一个小顶堆,大于mid的加入小顶堆,小于mid 的加入大顶堆若两堆相差2个数更新mid注意格式
#include <iostream> #include <algorithm> #include <cstdio> #include <set> #include <sstream> #include<string> #include<queue> #include<stack> #include<map> #include<cmath> #include<cctype> #include<cstring> #include<cstdlib> #define MAXX 100005 #define SIS std::ios::sync_with_stdio(false) #define ll long long #define INF 0x3f3f3f3f //#include<bits/stdc++.h> using namespace std; const int MAX =2e5+20; const double PI = 3.14159265359; int main() { int n,m,t; scanf("%d",&t); while(t--) { priority_queue<int> big; priority_queue<int ,vector<int>,greater<int> > small; scanf("%d %d",&n,&m); int mid,sum,x; printf("%d %d\n",n,(m+1)/2); for(int i=1;i<=m;i++) { scanf("%d",&x); if(i==1) { sum=1;mid=x; printf("%d ",mid); continue; } if(x<mid) big.push(x); else small.push(x); if(big.size()-small.size()==2) { small.push(mid); mid=big.top(); big.pop(); } else if(small.size()-big.size()==2) { big.push(mid); mid=small.top(); small.pop(); } if(i%2!=0) { sum++; if(sum%10!=0) printf("%d ",mid); else printf("%d\n",mid); } } if(sum%10!=0) printf("\n"); } return 0; }